#P1675G. Sorting Pancakes

Sorting Pancakes

Description

Nastya baked mm pancakes and spread them on nn dishes. The dishes are in a row and numbered from left to right. She put aia_i pancakes on the dish with the index ii.

Seeing the dishes, Vlad decided to bring order to the stacks and move some pancakes. In one move, he can shift one pancake from any dish to the closest one, that is, select the dish ii (ai>0a_i > 0) and do one of the following:

  • if i>1i > 1, put the pancake on a dish with the previous index, after this move ai=ai1a_i = a_i - 1 and ai1=ai1+1a_{i - 1} = a_{i - 1} + 1;
  • if i<ni < n, put the pancake on a dish with the following index, after this move ai=ai1a_i = a_i - 1 and ai+1=ai+1+1a_{i + 1} = a_{i + 1} + 1.

Vlad wants to make the array aanon-increasing, after moving as few pancakes as possible. Help him find the minimum number of moves needed for this.

The array a=[a1,a2,,an]a=[a_1, a_2,\dots,a_n] is called non-increasing if aiai+1a_i \ge a_{i+1} for all ii from 11 to n1n-1.

The first line of the input contains two numbers nn and mm (1n,m2501 \le n, m \le 250) — the number of dishes and the number of pancakes, respectively.

The second line contains nn numbers aia_i (0aim0 \le a_i \le m), the sum of all aia_i is equal to mm.

Print a single number: the minimum number of moves required to make the array aa non-increasing.

Input

The first line of the input contains two numbers nn and mm (1n,m2501 \le n, m \le 250) — the number of dishes and the number of pancakes, respectively.

The second line contains nn numbers aia_i (0aim0 \le a_i \le m), the sum of all aia_i is equal to mm.

Output

Print a single number: the minimum number of moves required to make the array aa non-increasing.

Samples

样例输入 1

6 19
5 3 2 3 3 3

样例输出 1

2

样例输入 2

3 6
3 2 1

样例输出 2

0

样例输入 3

3 6
2 1 3

样例输出 3

1

样例输入 4

6 19
3 4 3 3 5 1

样例输出 4

3

样例输入 5

10 1
0 0 0 0 0 0 0 0 0 1

样例输出 5

9

Note

In the first example, you first need to move the pancake from the dish 11, after which a=[4,4,2,3,3,3]a = [4, 4, 2, 3, 3, 3]. After that, you need to move the pancake from the dish 22 to the dish 33 and the array will become non-growing a=[4,3,3,3,3,3]a = [4, 3, 3, 3, 3, 3].