信夫くんと静夫くんは長方形の島で領地を取り合うゲームをしています。下の図①のように、島全体は格子状に区切られた正方形の区画でできており、区画にはそこから生じる損得が整数で示されています。
このゲームでは1つの駒を動かして領地の境界線を決めていきます。ゲーム開始時、駒は島の北西端にあります(図①)。この駒を島の南東端まで動かしていったときの駒の軌跡が領地の境界線となります。二人のプレーヤーは交互に駒を動かします。駒は南隣の格子点か東隣の格子点にのみ動かすことができます(図②)。駒が島の端に到達した場合は、南か東のうち動かせる方向に動かします。駒が南東端に到達したらゲーム終了です。
ゲーム終了後の境界線から北東側の領域が先攻プレーヤーの領域、南西側の領域が後攻プレーヤーの領 域です(図③)。各プレーヤーの領域内に含まれる、区画から生じる損得の合計がそのプレーヤーのス コアとなります。二人ともゲームにはかなり慣れており、最終的に自分のスコアから相手のスコアをひ いた値が一番大きくなるように正確に駒を動かします。
島の大きさとそれぞれの区画から生じる損得が与えられたとき、ゲーム終了時の結果を計算するプログラムを作成せよ。結果は、信夫くんと静夫くんのスコアの差の絶対値とする。
入力は以下の形式で与えられる。
W H s1,1 s1,2 ... s1,W s2,1 s2,2 ... s2,W : sH,1 sH,2 ... sH,W
1行目に島に含まれる東西方向と南北方向の区画の数 W, H (1 ≤ W, H ≤ 1000) が与えられる。続く H 行に i 行 j 列目の区画から生じる損得 si,j (-1000 ≤ si,j ≤ 1000) が与えられる。ただし、i の値が増加する方向を南、j の値が増加する方向を東とする。
信夫くんと静夫くんのスコアの差の絶対値を1行に出力する。
2 1 -2 1
1
2 2 2 -3 3 -1
3
5 4 5 3 2 -5 2 2 -4 2 8 -4 2 3 -7 6 7 3 -4 10 -3 -3
5