A11270 | Rudolf and k Bridges

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.

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.