Maximum Sum of Disjoint Pairs with Specific Difference

Given an array of integers and a number K, your task is to form pairs of elements from the array such that the absolute difference between them is strictly less than K, and the sum of these disjoint pairs is maximized.

Explanation:

The sum of a pair is the sum of its two elements. You need to find the maximum possible sum of all such disjoint pairs that can be formed.

Input:

T
N
ARR[]
K

Output:

Maximum sum of disjoint pairs for each test case in a new line.

Example:

Input:

ARR[] = {3, 5, 10, 15, 17, 12, 9}, K = 4

Output:

62

Explanation:

Disjoint pairs with differences less than K are (3, 5), (10, 12), and (15, 17). Their maximum sum is 3 + 5 + 10 + 12 + 15 + 17 = 62.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 3000
• 1 <= ARR[i] <= 1000
• 1 <= K < 1000
• Time limit: 1 sec

Note:

Multiple ways to form disjoint pairs are possible, but the sum should be maximized.