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 <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pq_int=priority_queue<int,vector<int>,greater<int>>;
const ll LINF=0x3fffffffffffffff;
const ll MOD=1000000007;
const ll MODD=0x3b800001;
const int INF=0x3fffffff;
#define _overload4(_1,_2,_3,_4,name,...) name
#define _overload3(_1,_2,_3,name,...) name
#define _rep1(n) _rep2(i,n)
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(ll i=a;i<b;++i)
#define _rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) _overload4(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__)
#define _rrep1(n) _rrep2(i,n)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(ll i=b-1;i>=a;i--)
#define _rrep4(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i:a)
#define sum(...) accumulate(range(__VA_ARGS__),0LL)
#define _range(i) (i).begin(),(i).end()
#define _range2(i,k) (i).begin(),(i).begin()+k
#define _range3(i,a,b) (i).begin()+a,(i).begin()+b
#define range(...) _overload3(__VA_ARGS__,_range3,_range2,_range)(__VA_ARGS__)
#define Yes(i) out(i?"Yes":"No")
#define YES(i) out(i?"YES":"NO")
//#define START auto start=system_clock::now()
//#define END auto end=system_clock::now();cerr<<duration_cast<milliseconds>(end-start).count()<<" ms\n"
#define elif else if
#define unless(a) if(!(a))
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
__attribute__((constructor)) void SETTINGS(){cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};
template<class T>
inline constexpr T gcd (T a,T b) {if(a==b)return a;else return gcd(b,(a-1)%b+1);}
template<class T>
inline constexpr T min(vector<T>& v){return *min_element(range(v));}
inline char min(string& v){return *min_element(range(v));}
template<class T>
inline constexpr T max(vector<T>& v){return *max_element(range(v));}
inline char max(string& v){return *max_element(range(v));}
template<typename T>
inline bool update_min(T& mn,const T& cnt){if(mn>cnt){mn=cnt;return 1;}else return 0;}
template<typename T>
inline bool update_max(T& mx,const T& cnt){if(mx<cnt){mx=cnt;return 1;}else return 0;}
inline void in() {}
template<class T>
istream& operator >> (istream& is, vector<T>& vec);
template<class T,size_t size>
istream& operator >> (istream& is, array<T,size>& vec);
template<class T,class L>
istream& operator >> (istream& is, pair<T,L>& p);
template<class T>
ostream& operator << (ostream& os, vector<T>& vec);
template<class T,class L>
ostream& operator << (ostream& os, pair<T,L>& p);
template<class T>
istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;}
template<class T,class L>
istream& operator >> (istream& is, pair<T,L>& p){is >> p.first;is >> p.second;return is;}
template<class T>
ostream& operator << (ostream& os, vector<T>& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;}
template<class T>
ostream& operator << (ostream& os, deque<T>& deq){os << deq[0];rep(i,1,deq.size()){os << ' ' << deq[i];}return os;}
template<class T,class L>
ostream& operator << (ostream& os, pair<T,L>& p){os << p.first << " " << p.second;return os;}
template <class Head, class... Tail>
inline void in(Head&& head,Tail&&... tail){cin>>head;in(move(tail)...);}
template <class T>
inline void out(T t){cout<<t<<'\n';}
inline void out(){cout<<'\n';}
template <class Head, class... Tail>
inline void out(Head head,Tail... tail){cout<<head<<' ';out(move(tail)...);}
template <class T>
inline void err(T t){cerr<<t<<'\n';}
inline void err(){cerr<<'\n';}
template <class Head, class... Tail>
inline void err(Head head,Tail... tail){cerr<<head<<' ';out(move(tail)...);}


ll w=1000,h=1000;
vv(ll,s,h,w);
vv(ll,mem,h,w,LINF);
ll dp(int y,int x){
    if(x==w||y==h)return 0;
    if(mem[y][x]-LINF)return mem[y][x];
    ll sum=0,sum2=0;
    rep(i,x,w)sum+=s[y][i];
    rep(i,y,h)sum2+=s[i][x];
    if((x+y)&1) return mem[y][x]=min(dp(y+1,x)+sum,dp(y,x+1)-sum2);
    else return mem[y][x]=max(dp(y+1,x)+sum,dp(y,x+1)-sum2);
}
signed main(){
    in(w,h);
    rep(h)rep(j,w)in(s[i][j]);
    out(abs(dp(0, 0)));
}