Illumination

problem

There is a light bulb at the grid point $(x, y)$ that meets $1 \ leq x \ leq h, 1 \ leq y \ leq w$.

The power supply is installed at coordinates $ (i + 0.5, j + 0.5) (1 \ leq i <h, 1 \ leq j <w, i + j $ is even) (corrected at 14:21). Coordinates $ When the power supply installed at (i + 0.5, j + 0.5) $ is turned on, the coordinates $(i, j), (i + 1, j), (i, j + 1), (i + 1) , j + 1)$ 4 $light bulbs in$ glow.

If you have more than $1$ connected to a power supply with a light bulb on $(i, j)$, you get $B_ {i, j}$ cleanliness. You have the total cleanliness. Also, if you turn on each power supply, it costs $W$ for electricity per $1$.

Turn on some power to maximize "total income-total electricity bill".

output

Output the maximum value of "total income-total electricity bill". Also, output a line break at the end.

Example

Input

4 4 10 100 100 100 100 100 100 100 100 1 100 100 1 1 1 1 1

Output

970

inputFormat

outputFormat

output

Output the maximum value of "total income-total electricity bill". Also, output a line break at the end.

Example

Input

4 4 10 100 100 100 100 100 100 100 100 1 100 100 1 1 1 1 1

Output

970

样例

4 4 10
100 100 100 100
100 100 100 100
1 100 100 1
1 1 1 1

970