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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int W,H,i,j;cin>>W>>H;
	static int dp[1001][1001];
	//1001^2のメモリを確保するので実質square1001(は?)
	static int yk[1001][1001]={};
	static int te[1001][1001]={};
	for(i=0;i<H;i++){
		for(j=0;j<W;j++){cin>>dp[i][j];}
	}
	for(i=0;i<H;i++){
		int gen=0;
		for(j=W-1;j>=0;j--){gen+=dp[i][j];yk[i][j]=gen;}
	}
	for(j=0;j<W;j++){
		int gen=0;
		for(i=H-1;i>=0;i--){gen+=dp[i][j];te[i][j]=gen;}
	}
	for(i=0;i<=H;i++){dp[i][W]=0;}
	for(j=0;j<=W;j++){dp[H][j]=0;}
	for(i=H-1;i>=0;i--){
		for(j=W-1;j>=0;j--){
			if((i+j)%2==0){dp[i][j]=max(dp[i+1][j]+yk[i][j],dp[i][j+1]-te[i][j]);}
			else{		   dp[i][j]=min(dp[i+1][j]+yk[i][j],dp[i][j+1]-te[i][j]);}
		}
	}
	cout<<abs(dp[0][0])<<endl;
	return 0;
}