#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int row, col;
int sum = 0;
int h[5000][200];
int v[5000][200];
const int INF = INT_MAX;
vector< vector< pair<int, int> > > Graph;
vector< vector< int > > dp;
#undef int
void init(int R, int C, int H[5000][200], int V[5000][200]) {
#define int long long
row = R;
col = C;
for(int i = 0; i < 5000; i++){
for(int j = 0; j < 200; j++){
h[i][j] = H[i][j];
v[i][j] = V[i][j];
}
}
if(C == 1){
for(int i = 0; i < row-1; i++){
sum += V[i][0];
}
return;
}
if(C == 2){
dp.resize(R, vector< int > (2));
return;
}
Graph.resize(R*C);
for(int i = 0; i < R; i++){
for(int j = 0; j < C-1; j++){
Graph[i*C+j].push_back(make_pair(i*C+j+1, H[i][j]));
Graph[i*C+j+1].push_back(make_pair(i*C+j, H[i][j]));
//Graph[i*C+j+1][i*C+j] = H[i][j];
}
}
for(int i = 0; i < R-1; i++){
for(int j = 0; j < C; j++){
Graph[i*C+j].push_back(make_pair((i+1)*C+j, V[i][j]));
//Graph[i*C+j][(i+1)*C+j] = V[i][j];
}
}
#undef int
}
void changeH(int P, int Q, int W) {
#define int long long
if(col == 1 || col == 2){
sum += W - h[P][Q];
h[P][Q] = W;
return;
}
for(auto &p : Graph[P*col+Q]){
if(p.first == P*col+Q+1){
p.second = W;
}
}
for(auto &p : Graph[P*col+Q+1]){
if(p.first == P*col+Q){
p.second = W;
}
}
#undef int
/*Graph[P*col+Q][P*col+Q+1] = W;
Graph[P*col+Q+1][P*col+Q] = W;*/
}
void changeV(int P, int Q, int W) {
#define int long long
if(col == 1 || col == 2){
sum += W - v[P][Q];
v[P][Q] = W;
return;
}
for(auto &p : Graph[P*col+Q]){
if(p.first == (P+1)*col+Q) p.second = W;
}
#undef int
//Graph[P*col+Q][(P+1)*col+Q] = W;
}
int escape(int V1, int V2) {
#define int long long
if(col == 1){
return sum;
}
if(col == 2){
dp.assign(row, vector< int > (col,INF));
dp[0][V1] = 0;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(i){
dp[i][j] = dp[i-1][j] + v[i-1][j];
}
}
dp[i][0] = min(dp[i][0], dp[i][1] + h[i][0]);
dp[i][1] = min(dp[i][1], dp[i][0] + h[i][0]);
}
return dp[row-1][V2];
}
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
vector< int > dist(row*col, INF);
dist[V1] = 0;
pq.push(make_pair(0,V1));
while(!pq.empty()){
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
//cout << node << ' ' << cost << endl;
if(dist[node] != cost) continue;
for(auto p : Graph[node]){
if(dist[p.first] > cost + p.second){
dist[p.first] = cost+p.second;
pq.push(make_pair(dist[p.first], p.first));
}
}
}
return dist[(row-1)*col+V2];
#undef int
}
