#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5005;
const int M = 205;
const int INF = 1e9;
const int L = 101;
const int K = (N + L - 1) / L + 5;

int n, m, k;
int h[N][M], v[N][M];
int t[4 * K][M][M];

void calc(int v, int l, int r, int a[M][M]) {
	for (int st = 0; st < m; ++st) {
		static int cur[M];
		for (int i = 0; i < m; ++i) {
			cur[i] = INF;
		}	
		cur[st] = 0;
		for (int i = l; i < r; ++i) {
			for (int j = 0; j < m - 1; ++j) {
				cur[j + 1] = min(cur[j + 1], cur[j] + h[i][j]);
			}
			for (int j = m - 1; j > 0; --j) {
				cur[j - 1] = min(cur[j - 1], cur[j] + h[i][j - 1]);
			}
			for (int j = 0; j < m; ++j) {
				cur[j] += ::v[i][j];
			}
		}
		for (int j = 0; j < m; ++j) {
			a[st][j] = cur[j];
		}
	}
	if ((v & 1) && v != 1) {
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < i; ++j) {
				swap(a[i][j], a[j][i]);
			}
		}
	}
}

void merge(int v, int a[M][M], int b[M][M], int c[M][M]) {
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < m; ++j) {
			c[i][j] = INF;
			for (int k = 0; k < m; ++k) {
				c[i][j] = min(c[i][j], a[i][k] + b[j][k]);
			}
		}
	}
	if ((v & 1) && v != 1) {
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < i; ++j) {
				swap(c[i][j], c[j][i]);
			}
		}
	}
}

void pull(int v) {
	merge(v, t[2 * v], t[2 * v + 1], t[v]);
}

void build(int v, int tl, int tr) {
	if (tr - tl == 1) {
		calc(v, tl * L, min(n - 1, tr * L), t[v]);
		return;
	}
	int tm = (tl + tr) / 2;
	build(2 * v, tl, tm);
	build(2 * v + 1, tm, tr);
	pull(v);
}

void updv(int v, int tl, int tr, int pos) {
	if (tr - tl == 1) {
		calc(v, tl * L, min(n - 1, tr * L), t[v]);
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos < tm * L) {
		updv(2 * v, tl, tm, pos);
	} else {
		updv(2 * v + 1, tm, tr, pos);
	}
	pull(v);
}

void updh(int v, int tl, int tr, int pos) {
	if (tr - tl == 1) {
		calc(v, tl * L, min(n - 1, tr * L), t[v]);
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos >= tl * L && pos < tm * L) {
		updh(2 * v, tl, tm, pos);
	}
	if (pos >= tm * L && pos < tr * L) {
		updh(2 * v + 1, tm, tr, pos);
	}
	pull(v);
}

void init(int grdn, int grdm, int grdh[5000][200], int grdv[5000][200]) {
	n = grdn;
	m = grdm;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m - 1; ++j) {
			h[i][j] = grdh[i][j];
		}
	}
	for (int i = 0; i < n - 1; ++i) {
		for (int j = 0; j < m; ++j) {
			v[i][j] = grdv[i][j];
		}
	}
	k = 0;
	for (int i = 0; i < n; i += L) {
		++k;
	}
	build(1, 0, k);
}

void changeH(int grdp, int grdq, int grdw) {
	int p = grdp, q = grdq, w = grdw;
	h[p][q] = w;
	updh(1, 0, k, p);
}

void changeV(int grdp, int grdq, int grdw) {
	int p = grdp, q = grdq, w = grdw;
	v[p][q] = w;
	updv(1, 0, k, p);
}

int escape(int grdv1, int grdv2) {
	int ret = t[1][grdv1][grdv2];
	for (int i = grdv2 + 1, sum = 0; i < m; ++i) {
		sum += h[n - 1][i - 1];
		ret = min(ret, t[1][grdv1][i] + sum);
	}
	for (int i = grdv2 - 1, sum = 0; i >= 0; --i) {
		sum += h[n - 1][i];
		ret = min(ret, t[1][grdv1][i] + sum);
	}
	return ret;
}