Rudolf and k Bridges

有一条 $n \times m$ 的河。第 $i$ 行第 $j$ 列的深度为 $a_{i, j}$。保证 $a_{i, 1} = a_{i, m} = 0$。 如果在第 $i$ 行第 $j$ 列安置桥墩，所需代价为 $a_{i, j} + 1$。 你需要选择连续的 $k$ 行，每行都要架起若干个桥墩，并满足以下条件： 1. 每行的第 $1$ 列必须架桥墩； 2. 每行的第 $m$ 列必须架桥墩； 3. 每行的相邻两个桥墩的距离不超过 $d$。其中 $(i, j_1)$ 和 $(i, j_2)$ 之间的距离为 $|j_1 - j_2| - 1$。 求最小代价和。

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.

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 $ .

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

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

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.