Maximum Sum of Minimum Values

You are given an array of n positive integers and an integer k. The task is to partition the array into k non-overlapping subarrays such that the sum of the minimum elements of each subarray is maximized. Notice that the optimal strategy is to isolate the k largest elements in their own individual subarrays. In other words, if sorted in descending order, the maximum sum is the sum of the first k elements.

The constraints are given as follows:

• \(1 \le n \le 1000\)
• \(1 \le k \le n\)
• \(1 \le arr[i] \le 10^9\) for all valid \(i\)

Design an algorithm that computes this sum efficiently.

inputFormat

The input is read from standard input and is structured as follows:

1. The first line contains two space‐separated integers, n and k.
2. The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer, which is the maximum possible sum of the minimum values of the k subarrays (effectively, the sum of the k largest numbers in the array).

6 2
5 6 2 4 7 1

13