Statement is not available in English language
E. Игра Кроша
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Крош обнаружил в своем любимом компьютере новую игру. В игре есть $$$n$$$ злобных морковных монстров, стоящих в ряд и пронумерованных от 1 до $$$n$$$. В начале Крош может атаковать только первого монстра. Чтобы сразиться с монстром номер $$$i$$$ ($$$1 \lt i \le n$$$), необходимо сначала победить всех монстров с номерами меньше $$$i$$$.

У Кроша есть супероружие — Импульсный Луч с радиусом действия $$$k$$$. Если Крош атакует монстра с номером $$$m$$$, то урон распределяется так:

  • монстр с номером $$$m$$$ получает $$$1$$$ единицу урона;
  • монстр с номером $$$(m+1)$$$ — 2 единицы урона;
  • монстр с номером $$$(m+2)$$$ — 3 единицы урона;
  • и так далее...
  • монстр с номером $$$(m+k-1)$$$ — $$$k$$$ урона (если он существует);

Другими словами, одним ударом Крош поражает подряд до $$$k$$$ монстров, при этом урон увеличивается на 1 с каждым последующим.

Монстры в этой игре также необычные. Если у монстра было $$$h_i \gt 0$$$ единиц здоровья, и он получил $$$d$$$ урона, то его новое здоровье станет равным $$$|h_i - d|$$$. Если здоровье становится равным нулю, монстр считается побежденным. Побежденные монстры больше не восстанавливаются, и их здоровье больше не изменяется, даже если последующие удары попадают по ним.

Если монстр, перед которым стоит Крош, побежден, он сразу перемещается к следующему живому монстру с наименьшим номером. Каждый удар Лучом можно наносить только по живому монстру, который стоит ближе всех к Крошу. При этом урон всё равно продолжают получать и побежденные монстры внутри радиуса действия Луча, если они попадают в соответствующие позиции — просто их здоровье остаётся равным нулю.

Игра завершается, когда Крош победит всех монстров. На каждый удар Лучом уходит ровно $$$1$$$ секунда.

У Кроша скоро встреча с Нюшей, и он хочет понять, успеет ли он пройти игру. Помогите Крошу посчитать минимальное количество секунд, которое потребуется для прохождения игры.

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

В первой строке дано $$$2$$$ целых числа $$$n,\ k\ (1 \le n \le 2 \cdot 10^5, 1 \le k \le 200)$$$ — количество монстров и радиус действия Импульсного Луча.

Во второй строке содержится $$$n$$$ чисел $$$h_1, h_2, \ldots, h_n\ (1 \le h_i \le 10^9)$$$ — начальное здоровье каждого монстра.

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

Выведите одно целое число — минимальное количество секунд, необходимое для победы над всеми монстрами.

Система оценки

В данной задаче будет $$$5$$$ групп тестов. Баллы начисляются при прохождении всех тестов из группы.

Группа тестовБаллыОграниченияНеобходимые подзадачи
$$$0$$$$$$0$$$Тесты из условия—
$$$1$$$$$$5$$$$$$n=1$$$—
$$$2$$$$$$10$$$$$$1 \le h_i \le 200$$$$$$0$$$
$$$3$$$$$$15$$$$$$k = 2$$$$$$1$$$
$$$4$$$$$$20$$$$$$n = k$$$, $$$1 \le n \le 200$$$$$$1$$$
$$$5$$$$$$50$$$—$$$0, 1, 2, 3, 4$$$
Примеры
Входные данные
1 1
5
Выходные данные
5
Входные данные
4 3
1 6 1 15
Выходные данные
8
Входные данные
7 3
1 20 11 42 23 52 10
Выходные данные
49
Примечание

$$$|x|$$$ — модуль числа $$$x$$$. Если $$$x \ge 0$$$, то $$$|x| = x$$$, а иначе $$$|x|=-x$$$.

Побежденные монстры учитываются при вычислении силы удара. Например, если Крош стоит перед рядом монстров $$$1, 2, 0, 10, 10$$$ и $$$k = 4$$$, то первые $$$4$$$ монстра (включая побежденного) получат удары $$$1, 2, 3, 4$$$ соответственно. После удара здоровье монстров будет $$$0, 0, 0, 6, 10$$$, и Крош переходит к монстру номер $$$4$$$ (бить «издалека» он не умеет).

В первом примере Крош нанесет $$$5$$$ раз ударит лучом по единственному монстру, пока он не исчезнет, поэтому ответ — $$$5$$$.

Во втором примере посмотрим, как изменяется здоровье монстров. Радиус действия луча — 3.

Кол-во атак$$$1$$$ монстр$$$2$$$ монстр$$$3$$$ монстр$$$4$$$ монстр
$$$0$$$$$$1$$$$$$6$$$$$$1$$$$$$15$$$
$$$1$$$$$$0$$$$$$4$$$$$$2$$$$$$15$$$
$$$2$$$$$$0$$$$$$3$$$$$$0$$$$$$12$$$
$$$3$$$$$$0$$$$$$2$$$$$$0$$$$$$9$$$
$$$4$$$$$$0$$$$$$1$$$$$$0$$$$$$6$$$
$$$5$$$$$$0$$$$$$0$$$$$$0$$$$$$3$$$

Первым ударом Крош побеждает первого монстра. Третий монстр получает удар силы $$$3$$$, и его здоровье становится равным $$$|1 - 3|=2$$$. Дальше Крош четыре раза бьет по второму монстру (побеждая вторым ударом монстра номер $$$3$$$), а монстр номер $$$4$$$ получает удары силы $$$3$$$.

Далее, когда остался живым только монстр номер $$$4$$$ с тремя единицами здоровья, надо сделать $$$3$$$ удара по нему. Суммарно понадобилось $$$5+3=8$$$ секунд.