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≤T≤10001≤K≤N≤5×105−109≤Ai≤109Sum of N over all test cases does not exceed 2×106
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.
