$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$ かかる.
いくつかの電源をオンにして「収入の合計 - 電気代の合計」を最大化しなさい.
入力は以下の形式で与えられる.
$h\ w \ W$
$B_{1,1} \dots B_{1,w}$
$\vdots$
$B_{h,1} \dots B_{h,w}$
「収入の合計 - 電気代の合計」の最大値を出力せよ. また, 末尾に改行も出力せよ.
4 4 10 100 100 100 100 100 100 100 100 1 100 100 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