Every year, Barr the Bear needs to chop some boards. This year, he decided to chop it during selection test.
This year, Barr the Bear is chopping a special board. Barr the bear has drawn lines on the board and divided it into N grids. In each grid, he has written a positive integer value in the grid.
Barr the Bear is going to make K chops on the board along the lines. In this way, there will be K+1 boards after chopping. Barr the Bear summed up the numbers in each board. This is called the value of the board. Then, he arranged the boards in a tower formation, whereby the boards are arranged from the top to the bottom in ascending order of the value of the boards. After this, Barr calculates the difference between any two adjacent boards in the tower, and added up all these differences. This value is called the Barr value.
Barr the Bear knows that he can maximise the Barr value by optimal chopping. However, he is lazy to think of how to do so. Can you help him?
Input
The first line contains two integers, N and K, denoting the number of grids and the number of chops respectively.
The next line contains N positive integers, denoting the numbers written on each grid from left to right.
Output
Output the maximum Barr value achievable.
Grading
For 40% of test data, N ≤ 1,000.
For 100% of test data, N ≤ 1,000,000.
For 100% of test data, K < N.
For 100% of test data, the N positive integers on the board are in the range 1 to 10,000.
Sample Input 1
5 3
5 7 9 3 1
Sample Output 1
15
Explanation for Sample Output 1
The optimal way is to chop the boards such that the boards are {5}, {7,9}, {3}, and {1}. Arranged in ascending order of value, the arrangement will be {1}, {3}, {5}, {7,9}. The difference between the first and second board is 2, between the second and third is 2, between the third and fourth is 11. Thus the Barr value is 2+2+11 = 15. This is the optimal solution.