Maximum Score Splitting Game

You are given a sequence of n nonnegative integers. You need to split the sequence into k+1 non-empty contiguous blocks by performing exactly k splitting operations.

In each splitting operation, you can choose any block which contains more than one element and select a pair of adjacent elements to split that block into two non‐empty blocks. When you split a block into two parts, if the sums of elements in the left and right parts are \(S_L\) and \(S_R\) respectively, you earn a score of \(S_L \times S_R\). Your task is to maximize the total score obtained after performing all k splits.

Note. Every split partitions a contiguous block into two contiguous subblocks. The final configuration will have k+1 blocks.

Formally, let the initial sequence be \(a_1,a_2,\dots,a_n\). You want to choose k positions (in a valid sequential construction) to partition the sequence into blocks. At each chosen split, if a block spanning indices \([l,r]\) is divided at an index \(i\) (where \(l \le i < r\)), then the score for that operation is \[ \left(\sum_{j=l}^{i}{a_j}\right) \times \left(\sum_{j=i+1}^{r}{a_j}\right). \] Your goal is to maximize the sum of scores over all splitting operations.

inputFormat

The first line contains two integers n and k separated by a space. The second line contains n nonnegative integers representing the sequence.

outputFormat

Output a single integer — the maximum total score that can be obtained.

sample

3 1
1 2 3

9