Smooth Surface Cut

After much effort, little A obtained a delicacy in the shape of a rectangular cuboid. Little A intends to cut the cake in half horizontally so as to share it with little B. Aesthetically, she wants the cut surface to be as smooth and harmonious as possible. To achieve this, she seeks your help to determine the optimal cutting plan.

The cake is modeled as a 3D lattice of points forming a cuboid of dimensions \(P\) (length), \(Q\) (width) and \(R\) (height). A point located at row \(x\), column \(y\) on the \(z\)th layer (with \(1 \le x \le P\), \(1 \le y \le Q\), \(1 \le z \le R\)) is denoted by \((x,y,z)\), and it is associated with a non-negative disharmony value \(v(x,y,z)\).

A valid cut surface is defined as a function \(f(x,y)\) where for each \(1 \le x \le P\) and \(1 \le y \le Q\), the chosen cut point \(f(x,y)\) satisfies \(1 \le f(x,y) \le R\). The cut surface must satisfy the following conditions:

• Completeness: For every vertical axis (there are \(P \times Q\) axes), the surface must intersect it exactly once.
• Smoothness: For any two adjacent vertical axes (neighbors in the grid, i.e. those with \(|x-x'|+|y-y'|=1\)), the difference in their cut points must be at most \(D\): \[ |f(x,y)-f(x',y')| \le D. \]

Among all valid cut surfaces, your task is to choose the one that minimizes the total disharmony value summed over all chosen points, i.e., minimize \[ \sum_{x=1}^{P}\sum_{y=1}^{Q} v(x,y,f(x,y)). \]

inputFormat

The first line of input contains four integers: \(P\), \(Q\), \(R\), and \(D\), where \(P, Q, R\) denote the dimensions of the cake and \(D\) is the maximum allowed difference between adjacent cut positions.

This is followed by \(R\) blocks of input. Each block represents one layer (from the first layer to the \(R\)th layer) and contains \(P\) lines. Each of these \(P\) lines contains \(Q\) non-negative integers. The \(j\)th number on the \(i\)th line of a block represents the disharmony value \(v(i,j,z)\) at layer \(z\).

outputFormat

Output a single integer representing the minimum total disharmony value achievable by a valid cut surface.

sample

2 2 3 1
1 2
3 4
2 1
4 3
3 4
1 2

9