#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
int R, C;
int H[100][5000], V[100][5000], DP[100][100][5000];
int temp[100];
inline void doDP(int u, int row = 0)
{
if(!row)
{
DP[u][u][0] = 0;
for(int i = u - 1; i >= 0; i--) DP[u][i][0] = DP[u][i + 1][0] + H[i][0];
if(u < (C - 1)) for(int i = u + 1; i < C; i++) DP[u][i][0] = DP[u][i - 1][0] + H[i - 1][0];
}
for(int i = row + !row; i < R; i++)
{
temp[0] = DP[u][0][i - 1] + V[0][i - 1];
for(int j = 1; j < C; j++)
{
temp[j] = min(temp[j - 1] + H[j - 1][i], DP[u][j][i - 1] + V[j][i - 1]);
}
int dp = DP[u][C - 1][i - 1] + V[C - 1][i - 1];
for(int j = C - 2; j >= 0; j--)
{
dp = min(dp + H[j][i], DP[u][j][i - 1] + V[j][i - 1]);
temp[j] = min(dp, temp[j]);
}
bool diff = false;
for(int j = 0; j < C; j++) if(temp[j] != DP[u][j][i]) {diff = true; break;}
if(!diff) break;
for(int j = 0; j < C; j++) DP[u][j][i] = temp[j];
}
return;
}
void init(int r, int c, int h[5000][200], int v[5000][200])
{
R = r;
C = c;
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++) {H[j][i] = h[i][j]; V[j][i] = v[i][j];}
}
for(int i = 0; i < C; i++) doDP(i);
return;
}
void changeH(int r, int c, int w)
{
H[c][r] = w;
for(int i = 0; i < C; i++) doDP(i, r);
return;
}
void changeV(int r, int c, int w)
{
V[c][r] = w;
for(int i = 0; i < C; i++) doDP(i, r + 1);
return;
}
int escape(int u, int v)
{
return DP[u][v][R - 1];
}
//int h[5000][200], v[5000][200];
//int main()
//{
// ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// int r, c;
// cin >> r >> c;
// for(int i = 0; i < r; i++)
// {
// for(int j = 0; j < (c - 1); j++) cin >> h[i][j];
// }
// for(int i = 0; i < (r - 1); i++)
// {
// for(int j = 0; j < c; j++) cin >> v[i][j];
// }
// init(r, c, h, v);
// int Q, t, u, v, w;
// cin >> Q;
// while(Q--)
// {
// cin >> t >> u >> v;
// if(t == 3) cout << escape(u, v) << '\n';
// else
// {
// cin >> w;
// if(t == 1) changeH(u, v, w);
// else changeV(u, v, w);
// }
// }
// return 0;
//}
