C. Чистка сугроба
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Мальчик Вася очень любит путешествовать. В частности, полёты на самолётах доставляют ему необычайное удовольствие. Он вот-вот должен был вылетать в другой город, но взлётную полосу сильно замело снегом, и она нуждается в очистке.

Взлётную полосу можно представить как $$$n$$$ последовательных участков, пронумерованных от $$$1$$$ до $$$n$$$. Метель была достаточно сильной, но уже прекратилась, поэтому Васе удалось вычислить, что $$$i$$$-й участок завален $$$a_i$$$ метрами снега. Для подобных ситуаций в аэропорте есть чистильщик, который работает достаточно необычным образом. За одну минуту чистильщик может сделать следующее:

  • Выбрать последовательный отрезок участков длины не более $$$d$$$ и убрать по метру снега с самых заваленных участков.

    Формально говоря, можно выбрать $$$1 \le l \le r \le n$$$ ($$$r - l + 1 \le d$$$). После этого вычисляется $$$c = \max \{ a_l, a_{l + 1}, \ldots , a_r \}$$$, и если $$$c \gt 0$$$, то для всех $$$i \colon l \le i \le r$$$ таких, что $$$a_i = c$$$, значение $$$a_i$$$ уменьшается на единицу.

Вася долго готовился к полёту и хочет понять, сколько времени ему осталось ждать до полной очистки всех участков от снега. Иначе говоря, требуется вычислить минимальное количество минут, которое придётся потратить чистильщику, чтобы добиться $$$a_i = 0$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$d$$$ ($$$1 \le n \le 5 \cdot 10^5, 1 \le d \le n$$$) — количество участков на взлётной полосе и максимальную длину участка, который может выбрать чистильщик.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ равно количеству метров снега на $$$i$$$ участке.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальное количество минут, необходимых чистильщику, чтобы добиться $$$a_i = 0$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$.

Пример
Входные данные
2
5 2
1 5 2 1 2
3 1
1000000000 1000000000 1000000000
Выходные данные
8
3000000000
Примечание

В первом наборе входных данных существует такая оптимальная последовательность операций. Сначала четыре раза выбрать отрезок $$$[2, 3]$$$. После трёх операций $$$a_2$$$ уменьшится до $$$2$$$, и массив $$$a$$$ будет иметь вид $$$[1, 2, 2, 1, 2]$$$. После четвёртой операции массив $$$a$$$ будет иметь вид $$$[1, 1, 1, 1, 2]$$$. Далее можно превратить массив в нули, выбирая отрезки $$$[1, 2]$$$, $$$[3, 3]$$$, $$$[5, 5]$$$ и $$$[4, 5]$$$ (именно в таком порядке).

Во втором наборе входных данных $$$d = 1$$$, а это значит, что каждый участок очищается независимо от других, и ответ равен сумме всех $$$a_i$$$.