The Château de Calberte is an ancient castle in France that fell into ruin after the knowledge of its construction was lost. It is high summer and you are volunteering at the Château to help historians repair its battlements.

The Château's battlements have ~N~ sections numbered ~1~ to ~N~ in order, where each section has been assigned a height ~h_i~. Each day, you will choose two sections ~L_j~ and ~R_j~ ~(L_j \le R_j)~ and increase the heights of all sections between them by ~1~, inclusive. If you can volunteer for up to ~K~ days, what is the minimum sum of absolute differences between all adjacent heights that can be achieved by the end?

Constraints

~1 \le N \le 10^5~

~1 \le K \le 10^9~

~1 \le h_i \le 10^4~

Subtask 1 [10%]

~K = 1~

Subtask 2 [30%]

~K \le 10^2~

Subtask 3 [60%]

No further constraints.

Input Specification

The first line of input will contain two space-separated integers, ~N~ and ~K~.

The next line of input will contain ~N~ space-separated integers, ~h_1, h_2, ..., h_N~.

Output Specification

Output one integer, the minimum sum of absolute differences between all adjacent heights.

Sample Input 1

3 3
3 1 6

Sample Output 1

2

Explanation for Sample Output 1

On the first and second days, choose ~L = 2~ and ~R = 2~. On the third day, choose ~L = 1~ and ~R = 2~. The resulting heights are ~[4, 4, 6]~ so the sum is ~|4 - 4| + |6 - 4| = 2~.

Sample Input 2

10 12
10 9 8 2 1 7 4 10 5 6

Sample Output 2

6