CF1941E.Rudolf and k Bridges

Bernard loves visiting Rudolf, but he is always running late. The problem is that Bernard has to cross the river on a ferry. Rudolf decided to help his friend solve this problem.

The river is a grid of $n$ rows and $m$ columns. The intersection of the $i$-th row and the $j$-th column contains the number $a_{i,j}$ — the depth in the corresponding cell. All cells in the first and last columns correspond to the river banks, so the depth for them is $0$.

The river may look like this.

Rudolf can choose the row $(i,1), (i,2), \ldots, (i,m)$ and build a bridge over it. In each cell of the row, he can install a support for the bridge. The cost of installing a support in the cell $(i,j)$ is $a_{i,j}+1$. Supports must be installed so that the following conditions are met:

1. A support must be installed in cell $(i,1)$;
2. A support must be installed in cell $(i,m)$;
3. The distance between any pair of adjacent supports must be no more than $d$. The distance between supports $(i, j_1)$ and $(i, j_2)$ is $|j_1 - j_2| - 1$.

Building just one bridge is boring. Therefore, Rudolf decided to build $k$ bridges on consecutive rows of the river, that is, to choose some $i$ ($1 \le i \le n - k + 1$) and independently build a bridge on each of the rows $i, i + 1, \ldots, i + k - 1$. Help Rudolf minimize the total cost of installing supports.

伯纳德很喜欢去拜访鲁道夫，但他总是迟到。问题在于，伯纳德必须乘坐渡轮横渡一条河流。鲁道夫决定帮助他的朋友解决这个问题。

这条河流是一个 $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$ 个连续行上建造 $k$ 座桥，即选择某个 $i$（满足 $1 \le i \le n - k + 1$），并在各行 $i, i + 1, \ldots, i + k - 1$ 上各自独立地建造一座桥。请帮助鲁道夫最小化所有桥墩的总安装成本。

The first line contains a single integer $t$ $(1 \le t \le 10^3)$ — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains four integers $n$, $m$, $k$, and $d$ ($1 \le k \le n \le 100$, $3 \le m \le 2 \cdot 10^5$, $1 \le d \le m$) — the number of rows and columns of the field, the number of bridges, and the maximum distance between supports.

Then follow $n$ lines, $i$-th line contains $m$ positive integers $a_{i, j}$ ($0 \le a_{i, j} \le 10^6$, $a_{i, 1} = a_{i, m} = 0$) — the depths of the river cells.

It is guaranteed that the sum of $n \cdot m$ for all sets of input data does not exceed $2 \cdot 10^5$.

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

For each test case, output a single number — the minimum total cost of supports installation.

对于每个测试用例，输出一个数字——支撑结构安装的最小总成本。

In the first test case, it is most profitable to build a bridge on the second row.

It is not a top view, but side view: gray cells — bridge itself, white cells are empty, black cells — supports, blue cells — water, brown cells — river bottom.

In the second test case, it is most profitable to build bridges on the second and third rows. The supports will be placed in cells $(2, 3)$, $(3, 2)$, and on the river banks.

In the third test case the supports can be placed along the river banks.

在第一个测试用例中，最有利可图的做法是在第二行建造一座桥。

这不是俯视图，而是侧视图：灰色格子表示桥体本身，白色格子为空，黑色格子为桥墩，蓝色格子为水面，棕色格子为河床。

在第二个测试用例中，最有利可图的做法是在第二行和第三行分别建造桥梁。桥墩将建在格子 $(2, 3)$、$(3, 2)$ 以及河岸上。

在第三个测试用例中，桥墩可以全部沿河岸布置。