Description

After much effort, Xiao A obtained a piece of qiegao. The qiegao is a rectangular cuboid, and Xiao A plans to cut it in half horizontally to share it with Xiao B. For aesthetic reasons, Xiao A hopes the cutting surface can be as smooth and harmonious as possible. So she asks you to find the best cutting plan.

For simplicity, we view the qiegao as a cuboid grid with length $P$, width $Q$, and height $R$. We call the point at layer $z$, row $x$, and column $y$ the point $(x,y,z)$, and it has a nonnegative disharmony value $v(x,y,z)$. A valid cutting surface satisfies the following two conditions:

• It has exactly one intersection with each vertical axis (there are $P \times Q$ vertical axes). That is, the cutting surface is a function $f(x,y)$, and for all $(x,y)$ ($x \in [1,P]$, $y \in [1,Q]$), we specify a cutting point $f(x,y)$ with $1 \le f(x,y) \le R$.

• The cutting surface needs to meet a smoothness requirement: cutting points on adjacent vertical axes cannot be too far apart. For all $1 \le x,x' \le P$ and $1 \le y,y' \le Q$, if $|x-x'|+|y-y'|=1$, then $|f(x,y)-f(x',y')| \le D$, where $D$ is a given nonnegative integer.

There may be many cutting surfaces $f$ satisfying the above conditions. Xiao A wants the one that minimizes the total disharmony value at the cutting points.

Input Format

The first line contains three positive integers $P,Q,R$, representing the length, width, and height of the qiegao.

The second line contains a nonnegative integer $D$, representing the smoothness requirement.

Then follow $R$ matrices of size $P$ rows and $Q$ columns. In the $z$-th matrix, the entry at row $x$ and column $y$ is $v(x,y,z)$ ($1 \le x \le P$, $1 \le y \le Q$, $1 \le z \le R$).

Output Format

Output a single integer, the minimal possible total disharmony value under the legality constraints.

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

6

Hint

Explanation for Sample 1

The optimal cutting surface $f$ is $f(1,1)=f(2,1)=2$, $f(1,2)=f(2,2)=1$.

Constraints

For $100\%$ of the testdata, $1 \le P,Q,R \le 40$, $0 \le D \le R$, and all given disharmony values do not exceed $1000$.

Translated by ChatGPT 5