Maximizing Division Cost

You are given an array of \(n\) positive integers \(a_1, a_2, \ldots, a_n\) and a positive integer \(k\). You need to divide the array into \(k\) non-empty subsequences (each subsequence is a sequence obtained by deleting some elements without changing the order of the remaining ones) such that each element belongs to exactly one subsequence.

For a subsequence whose elements (from the original array) have indices \(j_1 < j_2 < \cdots < j_\ell\), its value is defined as

[ f(j_1,\ldots,j_\ell)=\max_{1\le m\le \ell}\Bigl(a_{j_m}+m\Bigr). ]

The cost of a division is the sum of the values of the \(k\) subsequences. Find the maximum cost possible.

Note: It turns out that there is always an optimal division in which the \(k\) subsequences are contiguous segments of the original array. In other words, if you partition the array into \(k\) contiguous segments, then for each segment \([l,r]\) its value is computed as

[ f(l,r)=\max_{1\le m\le r-l+1}\Bigl(a_{l+m-1}+m\Bigr), ]

and the answer is the maximum sum we can obtain by choosing a partition \(1= i_0+1, i_1, \ldots, i_{k-1}, i_k=n\) and taking

[ \sum_{s=1}^{k} f(i_{s-1}+1,i_s). ]

You are given \(n\) and \(k\), along with the array. Compute the maximum cost possible.

inputFormat

The first line contains two integers \(n\) and \(k\) (with \(1 \le k \le n\)).

The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output a single integer, the maximum cost of dividing the array into \(k\) subsequences.

sample

3 2
5 3 4

12