• # For Solution

Alice has an integer sequence aa of length nn and all elements are different. She will choose a subsequence of aa of length mm, and defines the value of a subsequence ab1,ab2,,abmab1,ab2,…,abm as

i=1m(mabi)i=1mj=1mf(min(bi,bj),max(bi,bj)),∑i=1m(m⋅abi)−∑i=1m∑j=1mf(min(bi,bj),max(bi,bj)),

where f(i,j)f(i,j) denotes min(ai,ai+1,,aj)min(ai,ai+1,…,aj).

Alice wants you to help her to maximize the value of the subsequence she choose.

A sequence ss is a subsequence of a sequence tt if ss can be obtained from tt by deletion of several (possibly, zero or all) elements.

### Subsequence solution codeforces

The first line contains two integers nn and mm (1mn40001≤m≤n≤4000).

The second line contains nn distinct integers a1,a2,,ana1,a2,…,an (1ai<2311≤ai<231).

Output

Print the maximal value Alice can get.

### Subsequence solution codeforces

input

Copy
6 4
15 2 18 12 13 4

output

Copy
100


### Subsequence solution codeforces

Copy
11 5
9 3 7 1 8 12 10 20 15 18 5

output

Copy
176


### Subsequence solution codeforces

Copy
1 1
114514

output

Copy
0

input

Copy
2 1
666 888


### Subsequence solution codeforces

Copy
0

Note

In the first example, Alice can choose the subsequence [15,2,18,13][15,2,18,13], which has the value 4(15+2+18+13)(15+2+2+2)(2+2+2+2)(2+2+18+12)(2+2+12+13)=1004⋅(15+2+18+13)−(15+2+2+2)−(2+2+2+2)−(2+2+18+12)−(2+2+12+13)=100. On top of that, the subsequence [15,2,18,12][15,2,18,12] is also a possible answer.

In the second example, there are a variety of subsequences with value 176176, and one of them is [9,7,12,20,18][9,7,12,20,18].