题目描述
经过千辛万苦小 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) 。一个合法的切面满足以下两个条件:
- 与每个纵轴(一共有 P×Q 个纵轴)有且仅有一个交点。即切面是一个函数 f(x,y) ,对于所有 1≤x≤P,1≤y≤Q ,我们需指定一个切割点 f(x,y) ,且 1≤f(x,y)≤R 。
- 切面需要满足一定的光滑性要求,即相邻纵轴上的切割点不能相距太远。对于所有的 1≤x,x’≤P 和 1≤y,y’≤Q ,若 ∣x−x’∣+∣y−y’∣=1 ,则 ∣f(x,y)−f(x’,y’)∣≤D ,其中 D 是给定的一个非负整数。
可能有许多切面 f 满足上面的条件,小 A 希望找出总的切割点上的不和谐值最小的那个,即 ∑x,yv(x,y,f(x,y)) 最小。
输入格式
输入文件第一行是三个正整数 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) 。
输出格式
输出仅包含一个整数,表示在合法基础上最小的总不和谐值。
样例 1
2 2 2
1
6 1
6 1
2 6
2 6
6
第一组样例中最佳切面的 f 为 f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1 。
2 2 2
0
5 1
5 1
2 5
2 5
12
第二组样例中最佳切面的 f 为 f(1,1)=f(2,1)=f(1,2)=f(2,2)=1 。
数据范围与提示
对于 100% 的数据, P,Q,R≤40,0≤D≤R ,且给出的所有的不和谐值不超过 1000 。