You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

河流（river）

【题目描述】

小H门前有一条河，因此总是上课迟到，小L要帮他修座桥。

门前的河流是一条 $N \times M$ 的河流，第 $i$ 行第 $j$ 列的深度为 $a_{i,j}$,第一列和最后列中的所有单元格都与河岸相对应，因此它们的深度为 $0$ ,即保证 $a_{i,1}=a_{i,m}=0$。

小L可以选择 $(i,1),(i,2),..,(i,m)$ 行，并在上面架桥，在该行的每一个格子上，他都可以为桥安装支架，在 $(i,j)$ 格安装支架的花费是 $a_{i,j}+1$ 。在第$i$行安装的支架必须满足以下条件：

1. 必须在单元格 $(i,1),(i,m)$ 中安装支架
2. 任何两个相邻支架之间的距离不得大于 $d$ ,支架 $(i,j_1)$ 和 $(i,j_2)$ 之间的距离为 $|j_1-j_2|-1$

仅仅建造一个桥是不够的，所以小L决定连续建造 $k$ 座桥梁，即选择一些 $i(1 \le i \le n-k+1)$,在每一行上面独立建造一座桥。

小L没有很多钱，请帮他最小化建造费用。

【输入格式】

第一行包含4个整数 $n$,$m$,$k$,$d$ 字段的行数和列数、桥数以及支架之间的最大距离。

然后是 $n$ 行， 第$i$ 行包含 $m$ 个正整数 $a_{i, j}$ 河道单元的深度。

【输出格式】

输出支架安装的最低总成本。

###【样例输入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

【数据范围】

对于20%的数据，满足 $n \cdot m \le 100$。

另有10%的数据，满足 $d=1$

另有10%的数据，满足 $k=1$

对于100%的数据，满足 $1 \le k \le n \le 100$ ,$3 \le m \le 2 \cdot 10^5$ ,$1 \le d \le m$,$0 \le a_{i, j} \le 10^6$。

保证所有输入数据集的 $n \cdot m$ 之和不超过 $2 \cdot 10^5$ 。

时间限制 $1s$

空间限制 $512MB$