Problem Statement

We have a grid with $H$ horizontal rows and $W$ vertical columns. Each square contains an integer. The square $(i, j)$ at the $i$-th row from the top and $j$-th column from the left contains the integer $A_{i,j}$.

Takahashi will choose zero or more from the $H \times W$ squares and draw an X on each of them. An X is composed of a segment connecting the top-left and bottom-right corners, and a segment connecting the top-right and bottom-left corners.

Let us define Takahashi's score as $($the sum of integers contained in the squares on which X is drawn$) - C \times ($the minimum number of segments needed to draw the X's$)$.

Here, Takahashi can draw X's on diagonally adjacent squares at once.

For example, he can draw X's on the squares $(1, 1)$ and $(2, 2)$ with three segments:

• a segment connecting the top-left corner of $(1, 1)$ and the bottom-right corner of $(2, 2)$,
• a segment connecting the top-right corner of $(1, 1)$ and the bottom-left corner of $(1, 1)$,
• a segment connecting the top-right corner of $(2, 2)$ and the bottom-left corner of $(2, 2)$.

Find Takahashi's maximum possible score. Note that nothing should be drawn on unchosen squares.

Constraints

• $1 \leq H,W \leq 100$
• $1 \leq C \leq 10^9$
• $1 \leq A_{i,j} \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W C
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\hspace{1.5cm}\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}

Output

Print Takahashi's maximum possible score.