Rudolf 与 k 座桥

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

一条河可以表示为 $n$ 行 $m$ 列的网格。$a_{i,j}$ 表示第 $i$ 行第 $j$ 列的水深。第一列和最后一列是河岸，所以它们的水深均为 $0$。

在第 $i$ 行建桥时，可以在若干格子安装桥墩。在格子 $(i,j)$ 安装桥墩的费用是 $a_{i,j}+1$，并且必须满足：

• 第一列和最后一列必须安装桥墩；
• 任意相邻两个桥墩之间的距离不超过 $d$。位于列 $j_1,j_2$ 的桥墩之间的距离定义为 $|j_1-j_2|-1$。

你需要选择连续的 $k$ 行，并在每一行独立建一座桥。求所有桥墩的最小总费用。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

每个测试用例的第一行包含四个整数 $n,m,k,d$。接下来 $n$ 行，每行包含 $m$ 个整数，描述对应行的水深。

输出格式

对每个测试用例输出一行一个整数，表示连续 $k$ 座桥的最小总费用。

样例输入 1

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

样例输出 1

4
8
4
15
14

数据范围

$1\le t\le1000$，$1\le k\le n\le100$，$3\le m\le2\cdot10^5$，$1\le d\le m$，$0\le a_{i,j}\le10^6$，$a_{i,1}=a_{i,m}=0$。所有测试用例的 $n\cdot m$ 之和不超过 $2\cdot10^5$。