Problem: Nobuo-kun and Shizuo-kun are playing a game of competing for territories on a rectangular island. As shown in Fig. 1 below, the entire island is made up of square compartments divided in a grid pattern, and the profits and losses resulting from these are indicated by integers.

<image>



In this game, move one piece to determine the boundaries of the territory. At the beginning of the game, the piece is at the northwestern end of the island (Fig. ①). The trajectory of the piece when moving this piece to the southeastern end of the island becomes the boundary of the territory. The two players move the pieces alternately. Pieces can only be moved to the grid point next to the south or the grid point next to the east (Fig. 2). When the piece reaches the edge of the island, move it in the south or east direction. The game is over when the piece reaches the southeastern end.

The area on the northeast side of the boundary after the game is the area of ​​the first player, and the area on the southwest side is the area of ​​the second player (Fig. ③). The sum of the profits and losses generated from the parcels contained within each player's territory is that player's core. Both of them are quite accustomed to the game and move the pieces accurately so that the value obtained by subtracting the opponent's score from their own score is the largest in the end.




Create a program that calculates the outcome at the end of the game given the size of the island and the gains and losses that result from each parcel. The result is the absolute value of the difference between the scores of Nobuo-kun and Shizuo-kun.



Input

The input is given in the following format.


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


The first line gives the number of east-west and north-south sections contained in the island W, H (1 ≤ W, H ≤ 1000). The following row H is given the gains and losses si, j (-1000 ≤ si, j ≤ 1000) that arise from the compartments in row i and column j. However, the direction in which the value of i increases is south, and the direction in which the value of j increases is east.

Output

The absolute value of the difference between the scores of Nobuo-kun and Shizuo-kun is output in one line.

Examples

Input

2 1
-2 1


Output

1


Input

2 2
2 -3
3 -1


Output

3


Input

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


Output

5

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<functional>
#include<map>
#include<unordered_set>
using namespace std;
//int p = 998244353;
int p = 1000000007;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define rep(i,n) for(int i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define mmax(a,b) a=max(a,b)
#define mmin(a,b) a=min(a,b)
#define mkp make_pair
#define pin pair<int,int>
#define qin pair<int,pin>
#define V vector
#define Endl endl
#define veb vector<bool>
#define rev(s) reverse(s.begin(),s.end())
int max_kai = 150000;
vel kai(max_kai, 1);
vel inv_kai;
int rui(int a, int n) {
	if (n == 0) { return 1; }
	int x = rui(a, n / 2);
	x *= x; x %= p;
	if (n % 2 == 1) { x *= a; x %= p; }
	return x;
}
int inv(int a) { return rui(a, p - 2); }
void make_kai() {
	for (int i = 1; i < max_kai; i++) { kai[i] = kai[i - 1] * i; kai[i] %= p; }
	inv_kai = kai;
	rep(i, max_kai) { inv_kai[i] = inv(kai[i]); }
}
int nCr(int n, int r) {
	int a = kai[n] * inv_kai[r]; a %= p;
	a *= inv_kai[n - r]; a %= p;
	return a;
}
vel pa;
int root(int x) {
	if (pa[x] == -1) { return x; }
	int ans = root(pa[x]); pa[x] = ans;
	return ans;
}
void marge(int x, int y) {
	x = root(x);
	y = root(y);
	if (x != y) {pa[x] = y;}
}
#define lower(h,val) lower_bound(h.begin(),h.end(),val)-h.begin()
#define upper(h,val) upper_bound(h.begin(),h.end(),val)-h.begin()
int num_lp(int a, vel &nex) {
	unordered_set<int> se;
	int ans = 0;
	while (true) {
		if (se.find(a) != se.end()) {
			break;
		}
		se.insert(a);
		a = nex[a];
		ans++;
	}
	return ans;
}
int find_cr(int a, vel &nex) {
	unordered_set<int> se;
	while (true) {
		if (se.find(a) != se.end()) {break;}
		se.insert(a);
		a = nex[a];
	}
	return num_lp(a, nex);
}
int inf = 2000000000;
vvel dp;
int solve(vvel &sum, int i, int j, bool is_f) {
	int h = sum.size(); h--;
	int w = sum[0].size();
	if (i == h || j == w) { return 0; }
	if (dp[i][j] == inf) {
		int ans1 = solve(sum, i + 1, j, !is_f);
		int ans2 = solve(sum, i, j + 1, !is_f);
		ans2 += sum[i][j];
		if (is_f) {
			dp[i][j] = min(ans1, ans2);
		}
		else {
			dp[i][j] = max(ans1, ans2);
		}
	}
	return dp[i][j];
}
signed main(){
	int w, h; cin >> w >> h;
	vvel s(h, vel(w));
	int sum1 = 0;
	rep(i, h) {
		rep(j, w) {
			cin >> s[i][j];
			sum1 += s[i][j];
		}
	}
	vvel sum(h + 1, vel(w, 0));
	dp = vvel(h + 1, vel(w +1,inf));
	rep(j, w) {
		for (int i = h - 1; i >= 0; i--) {
			sum[i][j] = sum[i + 1][j] + s[i][j];
		}
	}
	cout << abs(solve(sum, 0, 0, true)*2-sum1) << endl;
	return 0;
}