G. Сортировка блинчиков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Настя испекла $$$m$$$ блинов и разложила по $$$n$$$ тарелкам. Тарелки стоят в одном ряду и пронумерованы слева направо. На тарелку с номером $$$i$$$ она положила $$$a_i$$$ блинчиков.

Увидев тарелки, Влад решил привнести порядок в стопки и переложить некоторые блинчики. За один ход он может переложить один блинчик с любой тарелки на соседнюю, то есть выбрать тарелку $$$i$$$ ($$$a_i > 0$$$) и сделать одно из следующих действий:

  • при $$$i > 1$$$ переложить блинчик на тарелку с предыдущим индексом, после такого действия $$$a_i = a_i - 1$$$ и $$$a_{i - 1} = a_{i - 1} + 1$$$;
  • при $$$i < n$$$ переложить блинчик на тарелку со следующим индексом, после такого действия $$$a_i = a_i - 1$$$ и $$$a_{i + 1} = a_{i + 1} + 1$$$.

Влад хочет сделать массив $$$a$$$ невозрастающим, переложив при этом как можно меньше блинчиков. Помогите ему найти минимальное количество перекладываний, необходимых для этого.

Массив $$$a=[a_1, a_2,\dots,a_n]$$$ называется невозрастающим, если $$$a_i \ge a_{i+1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$.

Входные данные

Первая строка входных данных содержит два числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 250$$$) — количество тарелок и количество блинчиков соответственно.

Вторая строка содержит $$$n$$$ чисел $$$a_i$$$ ($$$0 \le a_i \le m$$$), сумма всех $$$a_i$$$ равна $$$m$$$.

Выходные данные

Выведите единственное число — минимальное количество перекладываний, необходимое чтобы сделать массив $$$a$$$ невозрастающим.

Примеры
Входные данные
6 19
5 3 2 3 3 3
Выходные данные
2
Входные данные
3 6
3 2 1
Выходные данные
0
Входные данные
3 6
2 1 3
Выходные данные
1
Входные данные
6 19
3 4 3 3 5 1
Выходные данные
3
Входные данные
10 1
0 0 0 0 0 0 0 0 0 1
Выходные данные
9
Примечание

В первом примере нужно сначала переложить блинчик с тарелки $$$1$$$, после чего $$$a = [4, 4, 2, 3, 3, 3]$$$. После необходимо переложить блинчик с тарелки $$$2$$$ на тарелку $$$3$$$ и массив станет невозрастающим $$$a = [4, 3, 3, 3, 3, 3]$$$.