Question
Max Grab
You are given an array A of size N and an integer x = 0. In one move, select two indices i and j where i < j, add the larger of A[i] and A[j] to x, and remove that larger number from the array. If A[i] equals A[j], you may remove either and add that value to x. After performing this operation up to K times, determine the maximum possible value of x.
Input
The first line of the input contains two space-separated integers, N and K.
The second line of the input contains N space-separated integers.
Constraints
1 ≤ K < N ≤ 105
1 ≤ Ai ≤ 109
The second line of the input contains N space-separated integers.
Constraints
1 ≤ K < N ≤ 105
1 ≤ Ai ≤ 109
Output
Print the maximum possible value of x you can get.
Example
Sample Input
5 2
5 6 4 2 3
Sample Output
11
Explanation
In the first move, we choose i = 1 and j = 3. We get the max value of these as 5, and then we add it to x and remove it from the array. x = 5, A = [6, 4, 2, 3]
In the next and final move, we again choose indices i = 1, j = 3. Updated x = 11, A = [4, 2, 3]
5 2
5 6 4 2 3
Sample Output
11
Explanation
In the first move, we choose i = 1 and j = 3. We get the max value of these as 5, and then we add it to x and remove it from the array. x = 5, A = [6, 4, 2, 3]
In the next and final move, we again choose indices i = 1, j = 3. Updated x = 11, A = [4, 2, 3]