G: イルミネーション

問題

$1 \leq x \leq h , 1 \leq y \leq w$ をみたす格子点 $(x,y)$ に電球がある.

電源装置は座標 $(i+0.5,j+0.5) (1 \leq i < h,1 \leq j < w, i+j$ は偶数）に設置されている(14:21修正). 座標 $(i+0.5,j+0.5)$ に設置されている電源装置をオンにすると, 座標 $(i,j),(i+1,j),(i,j+1),(i+1,j+1)$ に存在する $4$ つの電球が光る.

$(i,j)$ にある電球がオンになっている電源装置に $1$ つ以上つながっていると, きれいさ $B_{i,j}$ を得られる. あなたは, きれいさの合計分の収入がもらえる. また, それぞれの電源装置をオンにすると, $1$ つあたり電気代が $W$ かかる.

いくつかの電源をオンにして「収入の合計 - 電気代の合計」を最大化しなさい.

制約

• $2 \leq h, w \leq 50$
• $0 \leq B_{i,j},W \leq 10^9$
• $h,w$ は偶数
• 入力はすべて整数

入力形式

入力は以下の形式で与えられる.

$h\ w \ W$
$B_{1,1} \dots B_{1,w}$
$\vdots$
$B_{h,1} \dots B_{h,w}$

出力

「収入の合計 - 電気代の合計」の最大値を出力せよ. また, 末尾に改行も出力せよ.

サンプル

サンプル入力 1

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

サンプル出力 1

970

以下のように $@$ の位置の電源をオンにし, $X$ の位置の電源をオフにするのが最善である.

100 100 100 100
   @       @
100 100 100 100
       @
1   100 100 1
   X       X
1   1   1   1