经过千辛万苦小 A 得到了一块切糕，切糕的形状是长方体，小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑，小 A 希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。

出于简便考虑，我们将切糕视作一个长 \(P\)、宽 \(Q\)、高 \(R\) 的长方体点阵。我们将位于第 \(z\) 层中第 \(x\) 行、第 \(y\) 列上的点称 \((x,y,z)\)，它有一个非负的不和谐值 \(v(x,y,z)\)。一个合法的切面满足以下两个条件：

• 与每个纵轴（一共有 \(P\times Q\) 个纵轴）有且仅有一个交点。即切面是一个函数 \(f(x,y)\)，对于所有 \((x,y)(x\in [1,P],y\in[1,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 希望找出总的切割点上的不和谐值最小的那个。

第一行是三个正整数 \(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)\)。

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

输入输出样例 1 解释

最佳切面的 \(f\) 为 \(f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1\)。

数据规模与约定

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