Description:


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

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

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

Input:


第一行是三个正整数P,Q,R,表示切糕的长P、 宽Q、高R。第二行有一个非负整数D,表示光滑性要求。接下来是R个P行Q列的矩阵,第z个 矩阵的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R)。
100%的数据满足P,Q,R≤40,0≤D≤R,且给出的所有的不和谐值不超过1000。

Output:


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

Sample Input:


Sample Output:


HINT:


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

题解:


恩这个题算是另一类的最小割吧。

我们考虑如果没有D的限制,怎样用最小割解决。

对于每一个点(x, y)建R+1个点连成一条链,其中第i个点和第i+1个点连边容量为v(x, y, i)。
然后S和每一个点(x, y, 1)相连,(x, y, R+1)和T相连。
这样就可以了(比较显然)

考虑有D的限制。

我们知道一个网络的最小割一定把原网络分成了两部分。设INF为无穷大,那么容量为INF的边代表两端点必须在一个部分里。
那么我们把(x, y, i)向(x, y-1, i-D)连一条容量为INF的边,然后(x, y+1), (x-1, y), (x+1, y)同理。

真是一个巧妙的做法╮(╯▽╰)╭。