A7012 | 鲁道夫与 k 座桥

伯纳德想去拜访鲁道夫，但他总是迟到，因为他必须乘渡轮过河。为了帮助朋友，鲁道夫决定在河上建桥。

这条河可以看作一个 $n$ 行 $m$ 列的网格。第 $i$ 行第 $j$ 列的单元格包含一个数字 $a_{i,j}$，表示该处的河水深度。第一列和最后一列代表河岸，因此它们的深度始终为 $0$。



鲁道夫可以选择某一行 $i$，并在该行建造一座桥。建桥需要在该行的若干个单元格中安装桥墩。在单元格 $(i, j)$ 安装桥墩的代价为 $a_{i,j} + 1$。
安装桥墩必须满足以下条件：

1. 必须在第 $1$ 列的单元格 $(i, 1)$ 安装桥墩；
2. 必须在第 $m$ 列的单元格 $(i, m)$ 安装桥墩；
3. 任意两个相邻桥墩之间的距离不能超过 $d$。具体来说，如果两个相邻桥墩分别位于 $(i, j_1)$ 和 $(i, j_2)$（假设 $j_1 j_2$），则它们之间的距离定义为 $|j_1 - j_2| - 1$。条件要求 $|j_1 - j_2| - 1 \le d$（即 $j_2 - j_1 \le d + 1$）。

只建一座桥太无聊了。因此，鲁道夫决定在连续的 $k$ 行上分别建造一座桥。也就是说，他需要选择一个起始行 $i$ ($1 \le i \le n - k + 1$)，并在第 $i, i+1, \dots, i+k-1$ 行上各建一座桥。

请你帮助鲁道夫计算，在满足上述条件的前提下，建造这 $k$ 座桥所需的桥墩安装总代价的最小值是多少。

第一行包含一个整数 $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$ 行，每行包含 $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$。

对于每组测试数据，输出一个整数，表示安装桥墩的最小总代价。