You are given an array $$A$$ of $$N$$ integers. You want to choose some integers from the array subject to the condition that the number of distinct integers chosen should not exceed $$K$$. Your task is to maximize the sum of chosen numbers.
You are given $$T$$ test cases.
Input format
- The first line contains a single integer $$T$$ denoting the number of test cases.
- The first line of each test case contains two space-separated integers $$N$$ and $$K$$ denoting the length of the array and the maximum number of distinct integers you can choose.
- The second line of each test case contains $$N$$ space-separated integers denoting the integer array $$A$$.
Output format
For each test case(in a separate line), print the maximum sum you can obtain by choosing some elements such that the number of distinct integers chosen is at most $$K$$. If you cannot choose any element, output $$0$$.
Constraints
$$ 1 \le T \le 1000 \\
1 \le K \le N \le 5 \times 10^5 \\
-10^9 \le A_i \le 10^9 \\
\text{Sum of N over all test cases does not exceed } 2 \times 10^6 $$
In the first test case, we have $$N = 4, K = 1$$, $$A = [3, -1, 2, 5]$$. Since we can choose atmost 1 distinct integer, we choose $$5$$. The sum is also $$5$$ and we output it.
In the second test case, we have $$N = 4, K = 2$$, $$A = [2, 1, 2, 5]$$. We need to choose atmost 2 distinct integers, we choose $$2, 2, 5$$. Note that the condition is choosing atmost $$K$$ distinct integers. So we can choose repeated number as many times as we want. The sum is $$2 + 2 + 5 = 9$$ and we output it.
