#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;
const int inf=1e9;
int n,m;
int rows[5007][207];
int cols[207][5007];
int dp[207][2][207];
int optl[207],optr[207];
int getsum(int row,int l,int r){
return rows[row][r]-rows[row][l-1];
}
void calcdp(){
for(int fin=1;fin<=m;fin++){
for(int c=1;c<=m;c++){
dp[fin][n%2][c]=getsum(n,min(c,fin),max(c,fin)-1);
}
for(int r=n-1;r>=1;r--){
optl[1]=dp[fin][1-r%2][1]+cols[1][r];
for(int c=2;c<=m;c++){
optl[c]=min(optl[c-1]+getsum(r,c-1,c-1),dp[fin][1-r%2][c]+cols[c][r]);
}
optr[m]=dp[fin][1-r%2][m]+cols[m][r];
for(int c=m-1;c>=1;c--){
optr[c]=min(optr[c+1]+getsum(r,c,c),dp[fin][1-r%2][c]+cols[c][r]);
}
for(int c=1;c<=m;c++){
dp[fin][r%2][c]=min(optl[c],optr[c]);
}
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
//void init(int R,int C,vector< vector<int> > H,vector< vector<int> > V){
n=R; m=C;
for(int i=1;i<=n;i++){
for(int f=1;f<=m-1;f++){
rows[i][f]=H[i-1][f-1];
rows[i][f]+=rows[i][f-1];
}
}
for(int i=1;i<=m;i++){
for(int f=1;f<=n-1;f++){
cols[i][f]=V[f-1][i-1];
}
}
calcdp();
}
void changeH(int P, int Q, int W) {
P++; Q++;
int dif=W-(rows[P][Q]-rows[P][Q-1]);
for(int i=Q;i<=m-1;i++){
rows[P][i]+=dif;
}
calcdp();
}
void changeV(int P, int Q, int W) {
P++; Q++;
cols[Q][P]=W;
calcdp();
}
int escape(int V1, int V2) {
V1++; V2++;
return dp[V2][1][V1];
}
/*int main(){
init(4,1,{{}},{{1},{1},{1},{1}});
cout<<escape(0,0)<<"\n";
changeV(0,0,2);
cout<<escape(0,0)<<"\n";
changeV(1,0,2);
cout<<escape(0,0)<<"\n";
changeV(2,0,2);
cout<<escape(0,0)<<"\n";
init(3,4,{{0,2,5},{7,1,1},{0,4,0}},{{0,0,0,2},{0,3,4,7}});
cout<<escape(2,1)<<"\n";
cout<<escape(3,3)<<"\n";
changeV(0,0,5);
changeH(1,1,6);
cout<<escape(2,1)<<"\n";
return 0;
}*/
