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:
Output Format:
For each test case, print the maximum beauty over all permutations of A.
Constraints:
1<=T<=10
1<=K<=N<=105
1<=A[i]<=103
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.