#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
map<int,map<int,map<int,map<int,int>>>> dp;
int n,m,h[5000][200],v[5000][200];
int ans(int r , int c , int en , int tag){
if(r == n-1 && c == en){
return 0;
}
if(dp.find(r) != dp.end() && dp[r].find(c) != dp[r].end() && dp[r][c].find(en) != dp[r][c].end() && dp[r][c][en].find(tag) != dp[r][c][en].end()){
return dp[r][c][en][tag];
}
int ret = 1000000000;
if(!tag){
if(c){
ret = min(ret,h[r][c-1]+ans(r,c-1,en,tag));
}
}else{
if(c+1 < m){
ret = min(ret,h[r][c]+ans(r,c+1,en,tag));
}
}
if(r+1 < n){
ret = min(ret,v[r][c]+min(ans(r+1,c,en,0),ans(r+1,c,en,1)));
}
return dp[r][c][en][tag] = ret;
}
void re(){
dp.clear();
}
void init(int R , int C , int H[5000][200] , int V[5000][200]){
n = R , m = C;
for(int i = 0 ; i < n ; i += 1){
for(int j = 0 ; j < m ; j += 1){
h[i][j] = H[i][j] , v[i][j] = V[i][j];
}
}
re();
}
void changeH(int P , int Q , int W){
h[P][Q] = W;
re();
}
void changeV(int P , int Q , int W){
v[P][Q] = W;
re();
}
int escape(int V1 , int V2){
return min(ans(0,V1,V2,0),ans(0,V1,V2,1));
}
