Mahamba wants to participate in International Olympiad in Informatics. In order to get a place in a national team, he must solve a simple programming task. The problem is that Mahamba has no idea how to solve it. So, as always, he asked you, the greatest programmer in Lalalandia, to help him!

You must divide the sequence A of length N into K consecutive segments so that each element is in only one segment and the sum of minimums of segments is maximum (see sample explanation for more details).

Input format

The first line contains N and K - the length of the sequence and the number of needed fragments respectively. The second line contains N numbers.

Output format

The only line of output should contain the answer to the problem.

Constraints

\(1 <= N <= 10^5\)

\(1 <= K <= min(N, 500)\)

\(0 <= A_i <= 10^9\) for each \(1 <= i <= N\)

P.S.: I discourage people to actually cheat on their exams. Use only your brain! =)