National Railway

Problem Description

dls's competitive-programming kingdom can be represented as a grid of $H$ rows and $W$ columns, where $(i, j)$ denotes the cell in the $i$-th row from the north and the $j$-th column from the west. The citizens recently asked the king to build a railway.

Building the railway has two stages:

1. Pick $2$ distinct cells from the whole grid and build a train station on each. Building a station on cell $(i, j)$ costs $A_{i,j}$.
2. Build a track between the two cells. If 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 wants to build a railway at minimum cost for his citizens. Find 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 following $H$ lines each contain $W$ integers, giving $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