#include <bits/stdc++.h>
#include "wombats.h"
#define ent '\n'

using namespace std;
typedef long long ll;

struct asd{
    int l, r, t[202][202], opt[202][202];
    asd(){
        l = r = 0;
        for(int i=0;i<202;i++){
            for(int j=0;j<202;j++){
                opt[i][j] = 200;
                t[i][j] = 1e9;
            }
        }
    }
};

int h[5050][205], v[5050][205];
int dp[5050][205];
int n, m, k, N;

asd merge(asd a, asd b){
    asd ans;
    ans.l = a.l, ans.r = b.r;
    for(int i = 0; i < m; i++){
        for(int j = m - 1; j >= 0; j--){
            int l = 0, r = min(ans.opt[i][j+1], m - 1);
            if(i > 0) l = ans.opt[i-1][j];
            for(int k = l; k <= r; k++){
                int val = a.t[i][k] + b.t[k][j] + v[a.r][k];
                if(val < ans.t[i][j]){
                    ans.t[i][j] = val;
                    ans.opt[i][j] = k;
                }
            }
        }
    }
    return ans;
}

asd calc(int l, int r){
    asd ans;
    ans.l = l, ans.r = r;
    for(int x=0;x<m;x++){
        for(int i=l;i<=r;i++){
            for(int j=0;j<m;j++)
                dp[i][j] = 1e9;
        }
        dp[l][x] = 0;
        for(int i=l;i<r;i++){
            for(int j=m-2;j>=0;j--){
                dp[i][j] = min(dp[i][j], dp[i][j+1] + h[i][j]);
            }
            for(int j=1;j<m;j++){
                dp[i][j] = min(dp[i][j], dp[i][j-1] + h[i][j-1]);
            }
            for(int j=0;j<m;j++){
                dp[i+1][j] = dp[i][j] + v[i][j];
            }
        }
        for(int j=m-2;j>=0;j--){
            dp[r][j] = min(dp[r][j], dp[r][j+1] + h[r][j]);
        }
        for(int j=1;j<m;j++){
            dp[r][j] = min(dp[r][j], dp[r][j-1] + h[r][j-1]);
        }
        for(int y=0;y<m;y++){
            ans.t[x][y] = dp[r][y];
        }
    }
    return ans;
}

asd t[250], a[66];

void build(int v, int tl, int tr){
    if(tl == tr){
        t[v] = a[tl];
    }
    else{
        int mid = tl + tr >> 1;
        build(v*2, tl, mid);
        build(v*2+1, mid+1, tr);
        if(v != 1) t[v] = merge(t[v*2], t[v*2+1]);
    }
}

void upd(int v, int tl , int tr, int pos){
    if(tl == tr){
        t[v] = a[pos];
    }
    else{
        int mid = tl + tr >> 1;
        if(pos <= mid){
            upd(v*2, tl, mid, pos);
        }
        else{
            upd(v*2+1, mid+1, tr, pos);
        }
        if(v != 1) t[v] = merge(t[v*2], t[v*2+1]);
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]){
    n = R, m = C;
    for(int i=0;i<n;i++){
        for(int j=0;j<m-1;j++){
            h[i][j] = H[i][j];
        }
    }
    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            v[i][j] = V[i][j];
        }
    }
    k = 83;
    for(int i=0;i<n;i+=k){
        int j = min(i + k - 1, n - 1);
        a[i / k] = calc(i, j);
        N = i / k;
    }
    build(1, 0 , N);
}

void changeH(int i, int j, int x){
    h[i][j] = x;
    a[i / k] = calc(i / k * k, min(n, (i + k) / k * k) - 1);
    upd(1, 0, N, i / k);
}

void changeV(int i, int j, int x){
    v[i][j] = x;
    a[i / k] = calc(i / k * k, min(n, (i + k) / k * k) - 1);
    upd(1, 0, N, i / k);
}

int escape(int vv, int u){
    if(N == 0) return a[0].t[vv][u];
    int ans = 1e9;
    for(int i=0;i<m;i++){
        ans = min(ans, t[2].t[vv][i] + t[3].t[i][u] + v[t[2].r][i]);
    }
    return ans;
}