Maximize Reversal Contribution

You are given a sequence of integers \(a_1,a_2,\ldots,a_n\) and an integer \(k\). Initially, there are partitions (barriers) at the two ends of the sequence. You may insert additional partitions at any positions (without overlapping) so that you can later select at most \(k\) pairs of partitions (the two partitions in a pair need not be originally adjacent) to perform a reversal on the subsequence between them. When two partitions become adjacent after all insertions, and the indices of the elements between them are \(l\) to \(r\), performing a reversal on that segment will yield a contribution computed according to the formula

[ \sum_{i=l}^{r} a_i \times (i-l+1) = \sum_{j=1}^{r-l+1} a_{r-j+1} \times j. ]

Note that the positions of the partitions remain unchanged, and each element can be reversed at most once (i.e. the reversal intervals must be non-overlapping). Your task is to choose at most \(k\) disjoint subarrays (which can be arbitrarily chosen by suitably inserting partitions) and reverse them so that the total contribution is maximized. It is allowed to perform fewer than \(k\) reversals (or even none), in which case the total contribution is the sum over the reversed segments only.

Input Format: The first line contains two integers \(n\) and \(k\). The second line contains \(n\) integers \(a_1,a_2,\ldots,a_n\).

Output Format: Output a single integer representing the maximum total contribution that can be achieved by performing at most \(k\) reversal operations.

Note: For a chosen segment from index \(l\) to \(r\), its contribution is computed as

[ \text{contribution}(l,r)=(r+1)\bigl(S[r]-S[l-1]\bigr)-\bigl(T[r]-T[l-1]\bigr), ]

where \(S[i]=a_1+\cdots+a_i\) and \(T[i]=1\cdot a_1+2\cdot a_2+\cdots+i\cdot a_i\). You are to decide the segmentation (by inserting partitions) and which segments to reverse to maximize the total contribution.

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space, where \(n\) is the length of the sequence and \(k\) is the maximum number of reversal operations you can perform. The second line contains \(n\) space-separated integers \(a_1,a_2,\ldots,a_n\).

outputFormat

Output a single integer denoting the maximum total contribution obtainable after performing at most \(k\) reversal operations.

sample

5 1
1 2 3 4 5

35