[Solved] Subsequence solution codeforces – 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

Subsequence solution codeforces

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

Input

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

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

Output

Print the maximal value Alice can get.

Subsequence solution codeforces

Examples
input

Copy
6 4
15 2 18 12 13 4

output

Copy
100

input

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

output

Copy
176

input

Copy
1 1
114514

output

Copy
0

input

Copy
2 1
666 888

output

Copy
0

Subsequence solution codeforces
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].

Also read : Counting Tuples codechef solution