#include "wombats.h"
#include<stdlib.h>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> P;
typedef pair<int,P> Pi;
int H[5000][200],V[5000][200];
int T[5000],T2[2][5000][2];
int R,C;
bool check[5000][200];
//55point;
void build2()
{
int i;
T2[0][0][0]=0,T2[0][0][1]=H[0][0];
for(i=1;i<R;i++){
if(T2[0][i-1][0]>T2[0][i-1][1]){
T2[0][i][1]=T2[0][i-1][1]+V[i-1][1];
T2[0][i][0]=min(T2[0][i][1]+H[i][0],T2[0][i-1][0]+V[i-1][0]);
}
else{
T2[0][i][0]=T2[0][i-1][0]+V[i-1][0];
T2[0][i][1]=min(T2[0][i][0]+H[i][0],T2[0][i-1][1]+V[i-1][1]);
}
}
T2[1][0][1]=0,T2[1][0][0]=H[0][0];
for(i=1;i<R;i++){
if(T2[1][i-1][0]>T2[1][i-1][1]){
T2[1][i][1]=T2[1][i-1][1]+V[i-1][1];
T2[1][i][0]=min(T2[1][i][1]+H[i][0],T2[1][i-1][0]+V[i-1][0]);
}
else{
T2[1][i][0]=T2[1][i-1][0]+V[i-1][0];
T2[1][i][1]=min(T2[1][i][0]+H[i][0],T2[1][i-1][1]+V[i-1][1]);
}
}
}
void init(int R, int C, int H_[5000][200], int V_[5000][200]){
int i,j;
for(i=0;i<R;i++)for(j=0;j<C-1;j++)H[i][j]=H_[i][j];
for(i=0;i<R-1;i++)for(j=0;j<C;j++)V[i][j]=V_[i][j];
::R=R;
::C=C;
if(C==1)for(i=1;i<R;i++)T[i]=T[i-1]+V[i-1][0];
if(C==2)build2();
}
void changeH(int P, int Q, int W){
H[P][Q]=W;
if(C==2)build2();
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
if(C==1)for(int i=P+1;i<R;i++)T[i]=T[i-1]+V[i-1][0];
if(C==2)build2();
}
int escape(int V1, int V2) {
if(C==1)return T[R-1];
if(C==2)return T2[V1][R-1][V2];
priority_queue <Pi,vector<Pi>,greater<Pi> > pq;
int i,j;
for(i=0;i<R;i++)for(j=0;j<C;j++)check[i][j]=0;
pq.push(Pi(0,P(0,V1)));
while(!pq.empty()){
Pi t=pq.top();
pq.pop();
if(check[t.Y.X][t.Y.Y])continue;
check[t.Y.X][t.Y.Y]=1;
if(t.Y.X == R-1 && t.Y.Y == V2)return t.X;
if(t.Y.Y!=C-1 && !check[t.Y.X][t.Y.Y+1])pq.push(Pi(t.X+H[t.Y.X][t.Y.Y],P(t.Y.X,t.Y.Y+1)));
if(t.Y.Y && !check[t.Y.X][t.Y.Y-1])pq.push(Pi(t.X+H[t.Y.X][t.Y.Y-1],P(t.Y.X,t.Y.Y-1)));
if(t.Y.X!=R-1 && !check[t.Y.X+1][t.Y.Y])pq.push(Pi(t.X+V[t.Y.X][t.Y.Y],P(t.Y.X+1,t.Y.Y)));
}
}
