#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
int n,c;
int h[5000][200],v[5000][200];
using mat=int[200][200];
mat dp;
void calc(int l,int r){
for(int i=0;i<c;i++){
for(int j=0;j<c;j++){
dp[i][j]=2e9;
}
dp[i][i]=0;
}
if(1<c){
for(int i=1;i<c;i++){
for(int j=0;j<i;j++){
dp[i][j]=min(dp[i][j],dp[i-1][j]+h[r][i-1]);
}
}
for(int i=c-2;0<=i;i--){
for(int j=c-1;i<j;j--){
dp[i][j]=min(dp[i][j],dp[i+1][j]+h[r][i]);
}
}
}
for(int i=r-1;l<=i;i--){
for(int j=0;j<c;j++){
for(int k=0;k<c;k++){
dp[j][k]+=v[i][j];
}
}
if(1<c){
for(int j=1;j<c;j++){
for(int k=0;k<c;k++){
dp[j][k]=min(dp[j][k],dp[j-1][k]+h[i][j-1]);
}
}
for(int j=c-2;0<=j;j--){
for(int k=0;k<c;k++){
dp[j][k]=min(dp[j][k],dp[j+1][k]+h[i][j]);
}
}
}
}
}
struct{
mat tree[800];
#define cur tree[node]
void build(int l,int r,int node){
if(r-l<100){
calc(l,r+1);
for(int i=0;i<c;i++){
for(int j=0;j<c;j++){
cur[i][j]=dp[i][j];
}
}
return;
}
int mid=(l+r)>>1,child=node<<1;
build(l,mid,child),build(mid+1,r,child|1);
for(int i=0;i<c;i++){
for(int j=0;j<c;j++){
cur[i][j]=INT_MAX;
for(int k=0;k<c;k++){
cur[i][j]=min(cur[i][j],tree[child][i][k]+tree[child|1][k][j]);
}
}
}
}
int P;
void update(int l,int r,int node){
if(r-l<100){
calc(l,r+1);
for(int i=0;i<c;i++){
for(int j=0;j<c;j++){
cur[i][j]=dp[i][j];
}
}
return;
}
int mid=(l+r)>>1,child=node<<1;
if(P<=mid)update(l,mid,child);
else update(mid+1,r,child|1);
for(int i=0;i<c;i++){
for(int j=0;j<c;j++){
cur[i][j]=INT_MAX;
for(int k=0;k<c;k++){
cur[i][j]=min(cur[i][j],tree[child][i][k]+tree[child|1][k][j]);
}
}
}
}
void update(int p){
P=p;
update(0,n-2,1);
}
}st;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n=R;
c=C;
for(int i=0;i<n;i++){
for(int j=0;j<c;j++){
h[i][j]=H[i][j];
v[i][j]=V[i][j];
}
}
st.build(0,n-2,1);
}
void changeH(int P, int Q, int W) {
h[P][Q]=W;
st.update(P);
}
void changeV(int P, int Q, int W) {
v[P][Q]=W;
st.update(P);
}
int escape(int V1, int V2) {
return st.tree[1][V1][V2];
}
