题目描述

辗迟喜欢拜访千钧，但他总是迟到。问题是辗迟必须乘渡船过河。千钧决定帮助他的朋友解决这个问题。

这条河是由 $n$ 行 $m$ 列组成的网格。第 $i$ 行和第 $j$ 列的交点包含数字 $a_{i,j}$--相应单元格的深度。第一列和最后一列中的所有单元格都与河岸相对应，因此它们的深度为 $0$ 。

千钧可以选择第 $(i,1),(i,2),...,(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$ 座桥，即选择一些 $i(1 \leq i \leq n-k+1)$，分别在每一行 $i,i+1,...,i+k-1$ 上建一座桥。

帮助千钧最小化安装支架的总成本。

输入格式

第一行包含四个整数 $n$ 、 $m$ 、 $k$ 和 $d$ -河的行数和列数、桥梁数以及支架之间的最大距离。$(1 \leq k \leq n \leq 100、3 \leq m \leq 2 * 10^5、1 \leq d \leq m)$

然后是 $n$ 行， 第 $i$ 行包含 $m$ 个正整数 $a_{i,j}(0 \leq a_{i,j} \leq 10^6，a_{i,1}=a_{i,m}= 0)$ --河道单元的深度。

输出格式

输出一个数字 - 支架安装的最低总成本。

样例

样例输入1

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

样例输出1

4

样例输入2

4 4 2 1
0 3 3 0
0 2 1 0
0 1 2 0
0 3 3 0

样例输出2

8

提示

在第一个测试案例中，在第二行建桥是最有利的。

这不是俯视图，而是​ 侧视图：灰色单元格--桥本身，白色单元格是空的，黑色单元格--支架，蓝色单元格--水，棕色单元格--河底。