Minimize Sum of Maximum Values

You are given an array of n integers and an integer k. Your task is to partition the array into exactly k non-empty subsequences such that the sum of the maximum values of these subsequences is minimized.

More formally, let the array be \(a = [a_1, a_2, \dots, a_n]\). You need to choose exactly \(k\) subsequences (each subsequence is a subset of the array and must be non-empty) so that if \(m_i\) is the maximum of the \(i\)-th subsequence, then the sum \(\sum_{i=1}^{k} m_i\) is as small as possible.

Hint: The optimal strategy is to assign the \(k\) largest numbers to separate subsequences, because these numbers will determine the maximums. The remaining numbers can be arbitrarily assigned.

Constraints: \(1 \leq k \leq n\).

inputFormat

The first line of input contains two space-separated integers (n) and (k), where (n) is the number of integers in the array and (k) is the number of subsequences. The second line contains (n) space-separated integers representing the array.

outputFormat

Output a single integer which is the minimized sum of the maximum values of the (k) subsequences.## sample

5 3
3 1 4 1 5

12