#include "wombats.h"
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm> 
#include <cstring>

#define X first
#define Y second
#define PB push_back

using namespace std; 

typedef pair<int, int> pii;

const int N = 5010;
const int M = 210;
const int S = 70;
const int OO = 2e9 + 10;

int n, m, h[N][M], v[N][M];

bool bio[N][M];
int dst[N][M], jmp[S + 10][M][M], best[M][M];

struct comp {
	bool operator () (const pii &a, const pii &b) const { 
		return dst[a.X][a.Y] > dst[b.X][b.Y];
	}
};

priority_queue<pair<int, pii>, vector<pair<int, pii>>> q;

void add(int a, int b, int c) {
	if(bio[a][b] || dst[a][b] <= c) { return; }
	dst[a][b] = c;
	q.push({-dst[a][b], {a, b}});
}

void jump() { 
	for(int k = 0; k < m; ++k) {
		for(int i = 0; i < S + 10; ++i) { 
			for(int j = 0; j < m; ++j) { 
				dst[i][j] = OO;
				bio[i][j] = 0;
			}
		}

		dst[0][k] = 0;
		q.push({-dst[0][k], {0, k}});
		for(; !q.empty(); ) { 
			int x = q.top().Y.X, y = q.top().Y.Y;
			q.pop();

			if(bio[x][y] || x == (n - 1 + S - 1) / S) { continue; }
			bio[x][y] = 1;
			for(int i = 0; i < m; ++i) { 
				add(x + 1, i, dst[x][y] + jmp[x][y][i]);
			}
		}

		for(int i = 0; i < m; ++i) { 
			best[k][i] = dst[(n - 1 + S - 1) / S][i];
		}
	}

//	for(int i = 0; i < m; ++i) {
//		for(int j = 0; j < m; ++j) { 
//			printf("%d%c", best[i][j], " \n"[j == m - 1]);
//		}
//	}
}

void dijkstra(int lo, int hi, int y) { 
	for(int i = 0; i <= hi; ++i) {
		for(int j = 0; j < m; ++j) { 
			bio[i][j] = 0;
			dst[i][j] = OO;
		}
	}
	
	dst[lo][y] = 0;
	q.push({-dst[lo][y], {lo, y}});
	for(; !q.empty(); ) { 
		int a = q.top().Y.X, b = q.top().Y.Y;
		q.pop();
		if(bio[a][b] || (a == hi && hi != n - 1)) { continue; }
		bio[a][b] = 1;
		
		if(a + 1 < n) { add(a + 1, b, dst[a][b] + v[a][b]); }
		if(b) { add(a, b - 1, dst[a][b] + h[a][b - 1]); }
		if(b + 1 < m) { add(a, b + 1, dst[a][b] + h[a][b]); }
	}
}

void blok(int x) { 
	for(int i = 0; i < m; ++i) { 
		int bnd = min((x / S + 1) * S, n - 1);
		dijkstra(x / S * S, bnd, i);
		for(int j = 0; j < m; ++j) { 
			jmp[x / S][i][j] = dst[bnd][j];
//			printf("%d: %d -> %d = %d\n", x / S, i, j, dst[bnd][j]);
		}
	}
}

void init(int rr, int cc, int hh[5000][200], int vv[5000][200]) {
	n = rr;
	m = cc;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m - 1; ++j) { 
			h[i][j] = hh[i][j];
		}
	}
	for(int i = 0; i < n - 1; ++i) { 
		for(int j = 0; j < m; ++j) { 
			v[i][j] = vv[i][j];
		}
	}

	for(int i = 0; i < n - 1; i += S) { 
		blok(i);
	}
}

void changeH(int p, int q, int w) {
	h[p][q] = w;
	blok(p);
	jump();
}

void changeV(int p, int q, int w) {
	v[p][q] = w;
	blok(p);
	jump();
}

int escape(int v1, int v2) {
    return jmp[0][v1][v2];
}