You are given an array \(A\) of length \(N\). You can select \(K\) distinct indexes and double the element in them.
The beauty of the array is the sum of any subarray of length \(K\). Find the maximum beauty over all permutations of array \(A\).
Input Format:
- The first line contains an integer \(T\), denoting the number of test cases.
- The first line of each test case contains two integers \(N\) and \(K\) respectively.
- The second line of each test case contains \(N\) space-separated integers, denoting the elements of the array.
Output Format:
For each test case, print the maximum beauty over all permutations of \(A\).
Constraints:
\(1 <= T <= 10\)
\(1 <= K <= N <= 10^5\)
\(1 <= A[i] <= 10^3\)
First test case:
We can select indexes \(2\), \(3\), and \(4\) (1-based indexing).
\(A\) becomes \([1, 8, 2, 6, 1]\). The permutation that gives maximum beauty is \([1, 8, 2, 6, 1]\). Hence, the answer is \(16\).
Second test case:
We can select index \(2\) (1-based indexing).
\(A\) becomes \([2, 10, 1]\). The permutation that gives maximum beauty is \([2, 10, 1]\). Hence, the answer is \(10\).
