Minimize Sum of Maximums in K Partitions

You are given an array of integers and an integer k. Your task is to partition the array into exactly k non-empty subarrays (not necessarily contiguous) such that the sum of the maximum element of each subarray is minimized.

This translates to choosing k elements from the array such that their sum is as small as possible under the constraint that these chosen elements will serve as the maximum of each partition. It can be shown that the optimal strategy is to take the k largest numbers from the array. In mathematical terms, if the array is sorted in descending order as \(a_1 \ge a_2 \ge \cdots \ge a_n\), then the minimum sum is given by:

[ \text{answer} = \sum_{i=1}^{k} a_i ]

Note that you should read input from stdin and write the answer to stdout.

inputFormat

The input is read from stdin in the following format:

1. 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 partitions.
2. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the minimized sum of the maximum elements from the k partitions. The output should be written to stdout.

5 2
1 3 2 4 5

9