#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;
const int bucket_sz=700;
const int inf=1e9;
int n,m;
int rows[5007][207];
int cols[207][5007];
int bucket[5007];
pair<int,int> seg[5007];
int dp[207][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(int buck,int from,int to){
for(int fin=1;fin<=m;fin++){
for(int c=1;c<=m;c++){
dp[buck][fin][to%2][c]=getsum(to,min(c,fin),max(c,fin)-1);
}
for(int r=to-1;r>=from;r--){
optl[1]=dp[buck][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[buck][fin][1-r%2][c]+cols[c][r]);
}
optr[m]=dp[buck][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[buck][fin][1-r%2][c]+cols[c][r]);
}
for(int c=1;c<=m;c++){
dp[buck][fin][r%2][c]=min(optl[c],optr[c]);
}
}
}
}
int dp2[207][2][207];
int dist(int buck,int from,int to){
return dp[buck][to][seg[buck].first%2][from];
}
void solve(){
for(int start=1;start<=m;start++){
for(int i=0;i<=n/bucket_sz;i++){
for(int c=1;c<=m;c++){
dp2[start][i%2][c]=inf;
if(i==0){
dp2[start][i%2][c]=dist(i,start,c);
continue;
}
for(int k=1;k<=m;k++){
dp2[start][i%2][c]=min(dp2[start][i%2][c],dist(i,k,c)+cols[k][seg[i-1].second]+dp2[start][1-i%2][k]);
}
}
}
}
}
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];
}
}
for(int i=1;i<=n;i++){
bucket[i]=i/bucket_sz;
if(seg[bucket[i]].first==0)seg[bucket[i]].first=i;
seg[bucket[i]].second=i;
}
for(int i=0;i<=n/bucket_sz;i++){
calcdp(i,seg[i].first,seg[i].second);
}
solve();
}
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(bucket[P],seg[bucket[P]].first,seg[bucket[P]].second);
solve();
}
void changeV(int P, int Q, int W){
P++; Q++;
cols[Q][P]=W;
if(bucket[P]==bucket[P+1]){
calcdp(bucket[P],seg[bucket[P]].first,seg[bucket[P]].second);
}
solve();
}
int escape(int V1, int V2) {
V1++; V2++;
return dp2[V1][(n/bucket_sz)%2][V2];
}
/*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;
}*/
