#include <bits/stdc++.h>
using namespace std;
#define OnlineJudge1
#define loop(x,a,n) for(int x = a;x < n;x++)
#define NumofDigits(n) ((int)log10(n)+1)
#define CountofNumber(array,n,x) (upper_bound(array, array+n, x)-lower_bound(array, array+n, x))
#define readline(s) getline(cin,s)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define EPS 1e-7
#define modulo ll (1e9 + 7)
const long double PI = 3.141592653589793238L;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,ll> pill;
typedef pair<ll,ll> pll;
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
for ( \
auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
blockTime.second; \
debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
)
void init(){
cin.tie(0);
ios::sync_with_stdio(0);
#ifdef OnlineJudge
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
}
const int N = 205, OO = 4e8;
int n, m, health, grid[N][N], dp[N][N], vis[N][N], vid;
int solve(int i, int j){
if(i == 0 && j == 0)
return health;
else if(i == -1 || j == -1)
return -OO;
int &ret = dp[i][j];
if(vis[i][j] == vid) return ret;
vis[i][j] = vid;
ret = grid[i][j] + max(solve(i - 1, j), solve(i, j - 1));
if(ret <= 0) return ret = -OO;
return ret;
}
int main(){
init();
cin >> n >> m;
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
cin >> grid[i][j];
int l = 1, r = OO;
while(l <= r){
vid++;
int mid = (l + r) / 2;
health = mid;
int can = solve(n - 1, m - 1);
if(can > 0)
r = mid - 1;
else
l = mid + 1;
}
cout << l;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBPbmxpbmVKdWRnZTEKCiNkZWZpbmUgbG9vcCh4LGEsbikgZm9yKGludCB4ID0gYTt4IDwgbjt4KyspCiNkZWZpbmUgTnVtb2ZEaWdpdHMobikgKChpbnQpbG9nMTAobikrMSkKI2RlZmluZSBDb3VudG9mTnVtYmVyKGFycmF5LG4seCkgICh1cHBlcl9ib3VuZChhcnJheSwgYXJyYXkrbiwgeCktbG93ZXJfYm91bmQoYXJyYXksIGFycmF5K24sIHgpKQojZGVmaW5lIHJlYWRsaW5lKHMpIGdldGxpbmUoY2luLHMpCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgRVBTIDFlLTcKI2RlZmluZSBtb2R1bG8gbGwgKDFlOSArIDcpCmNvbnN0IGxvbmcgZG91YmxlIFBJID0gMy4xNDE1OTI2NTM1ODk3OTMyMzhMOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGludCxsbD4gcGlsbDsKdHlwZWRlZiBwYWlyPGxsLGxsPiBwbGw7CgojZGVmaW5lIGRlYnVnKC4uLikgZnByaW50ZihzdGRlcnIsIF9fVkFfQVJHU19fKSwgZmZsdXNoKHN0ZGVycikKCiNkZWZpbmUgdGltZV9fKGQpIFwKICAgIGZvciAoIFwKICAgICAgICBhdXRvIGJsb2NrVGltZSA9IG1ha2VfcGFpcihjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCksIHRydWUpOyBcCiAgICAgICAgYmxvY2tUaW1lLnNlY29uZDsgXAogICAgICAgIGRlYnVnKCIlczogJWxsZCBtc1xuIiwgZCwgY2hyb25vOjpkdXJhdGlvbl9jYXN0PGNocm9ubzo6bWlsbGlzZWNvbmRzPihjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCkgLSBibG9ja1RpbWUuZmlyc3QpLmNvdW50KCkpLCBibG9ja1RpbWUuc2Vjb25kID0gZmFsc2UgXAogICAgKQoKdm9pZCBpbml0KCl7CiAgICBjaW4udGllKDApOwogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiNpZmRlZiBPbmxpbmVKdWRnZQogICAgZnJlb3BlbigiaW5wdXQudHh0IiwiciIsc3RkaW4pOwogICAgZnJlb3Blbigib3V0cHV0LnR4dCIsInciLHN0ZG91dCk7CiNlbmRpZgp9Cgpjb25zdCBpbnQgTiA9IDIwNSwgT08gPSA0ZTg7CmludCBuLCBtLCBoZWFsdGgsIGdyaWRbTl1bTl0sIGRwW05dW05dLCB2aXNbTl1bTl0sIHZpZDsKCmludCBzb2x2ZShpbnQgaSwgaW50IGopewogICAgaWYoaSA9PSAwICYmIGogPT0gMCkKICAgICAgICByZXR1cm4gaGVhbHRoOwogICAgZWxzZSBpZihpID09IC0xIHx8IGogPT0gLTEpCiAgICAgICAgcmV0dXJuIC1PTzsKICAgICAgICAKICAgIGludCAmcmV0ID0gZHBbaV1bal07CiAgICBpZih2aXNbaV1bal0gPT0gdmlkKSAgIHJldHVybiByZXQ7CiAgICAKICAgIHZpc1tpXVtqXSA9IHZpZDsKICAgIAogICAgcmV0ID0gZ3JpZFtpXVtqXSArIG1heChzb2x2ZShpIC0gMSwgaiksIHNvbHZlKGksIGogLSAxKSk7CgogICAgaWYocmV0IDw9IDApICAgIHJldHVybiByZXQgPSAtT087CiAgICAKICAgIHJldHVybiByZXQ7Cn0KaW50IG1haW4oKXsKICAgIGluaXQoKTsKCiAgICBjaW4gPj4gbiA+PiBtOwogICAgZm9yKGludCBpID0gMDtpIDwgbjtpKyspCiAgICAgICAgZm9yKGludCBqID0gMDtqIDwgbTtqKyspCiAgICAgICAgICAgIGNpbiA+PiBncmlkW2ldW2pdOwoKICAgIGludCBsID0gMSwgciA9IE9POwogICAgd2hpbGUobCA8PSByKXsKICAgICAgICB2aWQrKzsKICAgICAgICBpbnQgbWlkID0gKGwgKyByKSAvIDI7CiAgICAgICAgaGVhbHRoID0gbWlkOwogICAgICAgIGludCBjYW4gPSBzb2x2ZShuIC0gMSwgbSAtIDEpOwogICAgICAgIGlmKGNhbiA+IDApCiAgICAgICAgICAgIHIgPSBtaWQgLSAxOwogICAgICAgIGVsc2UKICAgICAgICAgICAgbCA9IG1pZCArIDE7CiAgICB9CgogICAgY291dCA8PCBsOwp9