After much effort, Little A has obtained a piece of cake in the shape of a rectangular cuboid. Little A intends to cut the cake in half to share with Little B. For aesthetic reasons, Little A wants the cut surface to be as smooth and harmonious as possible. She has come to you, hoping you can help her find the best cutting scheme.

For simplicity, we treat the cake as a grid of points with length $P$, width $Q$, and height $R$. A point located at row $x$, column $y$, and height $z$ ($1 \le x \le P$, $1 \le y \le Q$, $1 \le z \le R$) is denoted as $(x, y, z)$, and it has a non-negative "disharmony value" $v(x, y, z)$. A valid cut surface must satisfy the following two conditions:

1. It must intersect each vertical axis (there are $P \times Q$ such axes in total) exactly once. That is, the cut surface is a function $f(x, y)$, where for all $1 \le x \le P$ and $1 \le y \le Q$, we must specify a cutting point $f(x, y)$ such that $1 \le f(x, y) \le R$.
2. The cut surface must satisfy a certain smoothness requirement: the 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 non-negative integer.

There may be many cut surfaces $f$ that satisfy the above conditions. Little A wants to find the one that minimizes the total disharmony value of the cutting points, i.e., minimizes $\displaystyle \sum_{x, y} v(x, y, f(x, y))$.

Input

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

The second line contains a non-negative integer $D$, representing the smoothness requirement.

Following this are $R$ matrices, each with $P$ rows and $Q$ columns. The value at row $x$ and column $y$ of the $z$-th matrix is $v(x, y, z)$ ($1 \le x \le P, 1 \le y \le Q, 1 \le z \le R$).

Output

Output a single integer representing the minimum total disharmony value for a valid cut.

Examples

Input 1

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

Output 1

6

Note 1

In the first example, the optimal cut surface $f$ is $f(1, 1) = f(2, 1) = 2$ and $f(1, 2) = f(2, 2) = 1$.

Input 2

2 2 2
0
5 1
5 1
2 5
2 5

Output 2

12

Note 2

In the second example, the optimal cut surface $f$ is $f(1, 1) = f(2, 1) = f(1, 2) = f(2, 2) = 1$.

Subtasks

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