[HNOI2013]切糕

题目描述

经过千辛万苦小 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

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

输出样例 #1

6

说明

#### 输入输出样例 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$。