008 - 勢力の予想

問題

信夫くんと静夫くんは長方形の島で領地を取り合うゲームをしています。下の図①のように、島全体は格子状に区切られた正方形の区画でできており、区画にはそこから生じる損得が整数で示されています。

このゲームでは１つの駒を動かして領地の境界線を決めていきます。ゲーム開始時、駒は島の北西端にあります（図①）。この駒を島の南東端まで動かしていったときの駒の軌跡が領地の境界線となます。二人のプレーヤーは交互に駒を動かします。駒は南隣の格子点か東隣の格子点にのみ動かすことができます（図②）。駒が島の端に到達した場合は、南か東のうち動かせる方向に動かします。駒が南東端に到達したらゲーム終了です。

ゲーム終了後の境界線から北東側の領域が先攻プレーヤーの領域、南西側の領域が後攻プレーヤーの領域です（図③）。各プレーヤーの領域内に含まれる、区画から生じる損得の合計がそのプレーヤーのスコアとなります。二人ともゲームにはかなり慣れており、最終的に自分のスコアから相手のスコアをひいた値が一番大きくなるように正確に駒を動かします。

課題

島の大きさとそれぞれの区画から生じる損得が与えられたとき、ゲーム終了時の結果を計算するプログラムを作成せよ。結果は、信夫くんと静夫くんのスコアの差の絶対値とする。

入力

W H
s1,1 s1,2 ... s1,W
s2,1 s2,2 ... s2,W
.
.
.
sH,1 sH,2 ... sH,W

１行目に島に含まれる東西方向と南北方向の区画の数W,H(1≦W,H≦1000)が与えられる。続くH行にi行j列目の区画から生じる損得s_i,j(-1000≦s_i,j≦1000)が与えられる。ただし、iの値が増加する方向を南、jの値が増加する方向を東とする。

時間制限

入力に対して、実行時間が３秒を超えてはならない。

出力

信夫くんと静夫くんのスコアの差の絶対値を１行に出力する。

---

入出力例

入力例1

2 1
-2 1

出力例1

1

入力例2

2 2
2 -3
3 -1

出力例2

3

入力例3

5 4
5 3 2 -5 2
2 -4 2 8 -4
2 3 -7 6 7
3 -4 10 -3 -3

出力例3

5