题目描述

经过千辛万苦小 A 得到了一块切糕，切糕的形状是长方体，小 A 打算拦腰将切糕切成两半分给小 B 。出于美观考虑，小 A 希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。
出于简便考虑，我们将切糕视作一个长 $P$ 、宽 $Q$ 、高 $R$ 的长方体点阵。我们将位于第 $z$ 层中第 $x$ 行、第 $y$ 列上 $(1 \le x \le P, 1 \le y \le Q, 1 \le z \le R)$ 的点称为 $(x,y,z)$ ，它有一个非负的不和谐值 $v(x,y,z)$ 。一个合法的切面满足以下两个条件：

• 与每个纵轴(一共有 $P\times Q$ 个纵轴)有且仅有一个交点。即切面是一个函数 $f(x,y)$ ，对于所有 $1 \le x \le P, 1 \le y \le Q$ ，我们需指定一个切割点 $f(x,y)$ ，且 $1 \le f(x,y) \le R$ 。
• 切面需要满足一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有的 $1 \le x,x’ \le P$ 和 $1 \le y,y’ \le Q$ ，若 $|x-x’|+|y-y’|=1$ ，则 $|f(x,y)-f(x’,y’)| \le D$ ，其中 $D$ 是给定的一个非负整数。
  可能有许多切面 $f$ 满足上面的条件，小 A 希望找出总的切割点上的不和谐值最小的那个，即 $\sum_{x,y}{v(x, y, f (x, y))}$ 最小。

输入格式

输入文件第一行是三个正整数 $P$ , $Q$ , $R$ ，表示切糕的长 $P$ 、宽 $Q$ 、高 $R$ 。
第二行有一个非负整数 $D$ ，表示光滑性要求。
接下来是 $R$ 个 $P$ 行 $Q$ 列的矩阵，第 $z$ 个矩阵的第 $x$ 行第 $y$ 列是 $v(x,y,z) (1 \le x \le P, 1 \le y \le Q, 1 \le z \le R)$ 。

输出格式

输出仅包含一个整数，表示在合法基础上最小的总不和谐值。

2 2 2
1
6 1
6 1
2 6
2 6

6

2 2 2
0
5 1
5 1
2 5
2 5

12

数据范围与提示

对于 $100\%$ 的数据， $P,Q,R \le 40 , 0 \le D \le R$ ，且给出的所有的不和谐值不超过 $1000$ 。