E. Рудольф и k мостов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бернард любит ездить к Рудольфу в гости, но постоянно опаздывает. Проблема в том, что Бернард вынужден переплывать реку на пароме. Рудольф решил помочь своему другу решить эту проблему.

Река представляет собой клетчатое поле из $$$n$$$ строк и $$$m$$$ столбцов. На пересечении $$$i$$$-й строки и $$$j$$$-го столбца записано число $$$a_{i,j}$$$ — глубина в соответствующей клетке. Все клетки первого и последнего столбцов соответствуют берегам реки, поэтому глубина в них $$$0$$$.

Река может выглядеть так.

Рудольф может выбрать строку $$$(i,1), (i,2), \ldots, (i,m)$$$ и построить над ней мост. В каждой клетке строки он может установить опору для моста. Стоимость установки опоры в клетке $$$(i,j)$$$ равна $$$a_{i,j}+1$$$. Опоры необходимо установить так, чтобы были выполнены следующие условия:

  1. В клетке $$$(i,1)$$$ должна быть установлена опора;
  2. В клетке $$$(i,m)$$$ должна быть установлена опора;
  3. Расстояние между любой парой соседних опор должно быть не больше $$$d$$$. Расстояние между опорами $$$(i, j_1)$$$ и $$$(i, j_2)$$$ равно $$$|j_1 - j_2| - 1$$$.

Построить один мост это скучно. Поэтому Рудольф решил построить $$$k$$$ мостов на последовательных строках реки, то есть выбрать некоторое $$$i$$$ ($$$1 \le i \le n - k + 1$$$) и независимо построить по мосту на каждой из строк $$$i, i + 1, \ldots, i + k - 1$$$. Помогите Рудольфу минимизировать суммарную стоимость установки опор.

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

Первая строка содержит одно целое число $$$t$$$ $$$(1 \le t \le 10^3)$$$ — количество наборов входных данных. Далее следуют описания наборов.

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

Далее следует $$$n$$$ строк, $$$i$$$-я строка содержит $$$m$$$ целых положительных чисел $$$a_{i, j}$$$ ($$$0 \le a_{i, j} \le 10^6$$$, $$$a_{i, 1} = a_{i, m} = 0$$$) — глубины клеток реки.

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

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

Для каждого набора входных данных выведите одно число — минимальную суммарную стоимость опор.

Пример
Входные данные
5
3 11 1 4
0 1 2 3 4 5 4 3 2 1 0
0 1 2 3 2 1 2 3 3 2 0
0 1 2 3 5 5 5 5 5 2 0
4 4 2 1
0 3 3 0
0 2 1 0
0 1 2 0
0 3 3 0
4 5 2 5
0 1 1 1 0
0 2 2 2 0
0 2 1 1 0
0 3 2 1 0
1 8 1 1
0 10 4 8 4 4 2 0
4 5 3 2
0 8 4 4 0
0 3 4 8 0
0 8 1 10 0
0 10 1 5 0
Выходные данные
4
8
4
15
14
Примечание

В первом наборе тестовых данных выгоднее всего построить мост на второй строке.

Это не вид сверху, а вид сбоку: серые ячейки — сам мост, белые ячейки — пустые, черные ячейки — опоры, синие ячейки — вода, коричневые ячейки — дно реки.

Во втором наборе мост выгоднее всего построить на второй и третьей строках. Опоры будут стоять в клетках $$$(2, 3)$$$, $$$(3, 2)$$$ и на берегах.

В третьем наборе опоры можно расположить по берегам.