Minimized Sum of Maximums

You are given an integer array of length \(n\) and a positive integer \(k\). You are allowed to rearrange the array arbitrarily, and then split the array into \(k\) contiguous subarrays. For each subarray, consider its maximum element. The goal is to minimize the sum of these maximum elements.

More formally, let \(a_1, a_2, \ldots, a_n\) be the elements of the array after rearrangement, and let \(S_1, S_2, \ldots, S_k\) be \(k\) contiguous subarrays that partition the array. Define \(m_i = \max(S_i)\) for \(1 \leq i \leq k\). You are required to compute the value of \(\sum_{i=1}^{k} m_i\) such that this sum is minimized. It turns out that the optimal strategy is to sort the array in ascending order and then take the sum of the largest \(k\) elements.

inputFormat

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

outputFormat

Output a single integer: the minimized sum of the maximum elements of the \(k\) contiguous subarrays after an optimal rearrangement.

7 3
4 2 1 10 5 8 6

24