National Railway

Problem Description

dls's competitive-programming kingdom can be represented as a grid with $H$ rows and $W$ columns. We denote by $(i, j)$ the cell in the $i$-th row from the north and the $j$-th column from the west. Recently the citizens of this kingdom hope the king will build a railway.

Building a railway happens in two stages:

1. Choose 2 different cells from all the cells, and build a train station on each of them. The cost to build a station on cell $(i, j)$ is $A_{i,j}$.
2. Build a rail between these two cells. Suppose the chosen cells are $(x_1, y_1)$ and $(x_2, y_2)$; the cost is $C \times (|x_1 - x_2| + |y_1 - y_2|)$.

dls's wish is to build a railway at the minimum cost to benefit the citizens. Now please compute this minimum cost.

Input Format

The first line contains three integers $H, W, C$ ($2 \leq H, W \leq 1000$, $1 \leq C \leq 10^9$).

The next $H$ lines each contain $W$ integers, representing $A_{i,j}$ ($1 \leq A_{i,j} \leq 10^9$).

Output Format

Output one integer, the minimum cost.

Sample Input 1

3 4 2
1 7 7 9
9 6 3 7
7 8 6 4

Sample Output 1

10

Sample Input 2

3 3 1000000000
1000000 1000000 1
1000000 1000000 1000000
1 1000000 1000000

Sample Output 2

1001000001