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

Вам даны два массива: массив $$$a$$$, состоящий из $$$n$$$ нулей и массив $$$b$$$, состоящий из $$$n$$$ целых чисел.

Вы можете применить к массиву $$$a$$$ следующую операцию произвольное количество раз: выбрать какой-то подотрезок $$$a$$$ длины $$$k$$$ и добавить арифметическую прогрессию $$$1, 2, \ldots, k$$$ к этому подотрезку — то есть добавить $$$1$$$ к первому элементу подотрезка, $$$2$$$ ко второму элементу и так далее. Выбранный подотрезок должен находиться внутри границ массива $$$a$$$ (если левая граница выбранного подотрезка равна $$$l$$$, тогда должно выполняться условие $$$1 \le l \le l + k - 1 \le n$$$). Заметьте, что добавляемая прогрессия всегда имеет вид $$$1, 2, \ldots, k$$$, а не $$$k, k - 1, \ldots, 1$$$ или какой-нибудь другой (то есть самый левый элемент всегда увеличивается на $$$1$$$, второй элемент всегда увеличивается на $$$2$$$ и так далее).

Ваша задача — найти минимально возможное количество операций, необходимое для того, чтобы удовлетворить условие $$$a_i \ge b_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$. Заметьте, что условие $$$a_i \ge b_i$$$ должно быть выполнено для всех элементов сразу.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) — количество элементов в обоих массивах и длину подотрезка соответственно.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$), где $$$b_i$$$ — это $$$i$$$-й элемент массива $$$b$$$.

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

Выведите одно целое число — минимально возможное количество операций, необходимое для того, чтобы удовлетворить условие $$$a_i \ge b_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$.

Примеры
Входные данные
3 3
5 4 6
Выходные данные
5
Входные данные
6 3
1 2 3 2 2 3
Выходные данные
3
Входные данные
6 3
1 2 4 1 2 3
Выходные данные
3
Входные данные
7 3
50 17 81 25 42 39 96
Выходные данные
92
Примечание

Рассмотрим первый тестовый пример. В этом тесте у нас нет никакого выбора, кроме как добавить пять прогрессий для того, чтобы сделать первый элемент массива равным $$$5$$$. В этом случае массив $$$a$$$ будет равен $$$[5, 10, 15]$$$.

Рассмотрим второй тестовый пример. В этом тесте давайте добавим одну прогрессию на отрезке $$$[1; 3]$$$ и две прогрессии на отрезке $$$[4; 6]$$$. В этом случае массив $$$a$$$ будет равен $$$[1, 2, 3, 2, 4, 6]$$$.