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

using namespace std;

int dp[5000][200], HH[5000][200], VV[5000][200];
int RR, CC;
const int K = 31;
int fuck[100][200][200];
int ans[200][200];

void recalc_block(int ind) {
    int row_start = ind * (K - 1), row_endd = min(RR - 1, (ind + 1) * (K - 1));
    //cout << "rcbl " << ind << ' ' << row_start << ' ' << row_endd << '\n';
    for (int JJ = 0; JJ < CC; JJ++) {
        vector<vector<int>> dp(row_endd - row_start + 1, vector<int>(CC, 0));
        for (int j1 = JJ - 1; j1 >= 0; j1--) {
            dp.back()[j1] = dp.back()[j1 + 1] + HH[row_endd][j1];
        }
        for (int j1 = JJ + 1; j1 < CC; j1++) {
            dp.back()[j1] = dp.back()[j1 - 1] + HH[row_endd][j1 - 1];
        }
        for (int i = row_endd - 1; i >= row_start; i--) {
            for (int j = 0; j < CC; j++) {
                dp[i - row_start][j] = dp[i - row_start + 1][j] + VV[i][j];
            }
            for (int j = 1; j < CC; j++) {
                dp[i - row_start][j] = min(dp[i - row_start][j], dp[i - row_start][j - 1] + HH[i][j - 1]);
            }
            for (int j = CC - 2; j >= 0; j--) {
                dp[i - row_start][j] = min(dp[i - row_start][j], dp[i - row_start][j + 1] + HH[i][j]);
            }
        }
        //cout << JJ << ":\n";
        for (int j = 0; j < CC; j++) fuck[ind][j][JJ] = dp[0][j];
        // for (int j = 0; j < CC; j++) {
        //     cout<<ind << ' ' << j << ' ' << JJ << ' ' << fuck[ind][j][JJ] << '\n';
        // }
        // cout << '\n';
    }
}

void calc_answers() {
    int lb = -1;
    for (int i = 0; i < 100; i++) {
        if (i * (K - 1) >= RR - 1) break;
        lb = i;
    }
    //cout << "calc " << lb << '\n';
    for (int JE = 0; JE < CC; JE++) {
        vector<int> curdp(CC);
        for (int j = 0; j < CC; j++) curdp[j] = fuck[lb][j][JE];
        vector<int> newdp(CC);
        for (int i = lb - 1; i >= 0; i--) {
            //cout << "yessir\n";
            for (int j = 0; j < CC; j++) {
                newdp[j] = 2e9 + 1;
                for (int j2 = 0; j2 < CC; j2++) newdp[j] = min(newdp[j], curdp[j2] + fuck[i][j][j2]);
            }
            swap(newdp, curdp);
        }
        for (int j = 0; j < CC; j++) {
            ans[j][JE] = curdp[j];
        }
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    RR=R;
    CC=C;
    for(int i=0;i<5000;i++){
        for (int j = 0; j < 200; j++) {
            HH[i][j] = H[i][j];
            VV[i][j] = V[i][j];
        }
    }
    for (int i = 0; i < 100; i++) {
        if (i * (K - 1) >= RR - 1) break;
        recalc_block(i);
    }
    calc_answers();
}

void changeH(int P, int Q, int W) {
    HH[P][Q] = W;
    for (int i = 0; i < 100; i++) {
        if (i * (K - 1) >= max(P + 1, RR - 1)) break;
        if (i * (K - 1) <= P && P <= min(RR - 1, (i + 1) * (K - 1))) recalc_block(i);
    }
    calc_answers();
}

void changeV(int P, int Q, int W) {
    VV[P][Q] = W;
    for (int i = 0; i < 100; i++) {
        if (i * (K - 1) >= RR - 1) break;
        if (i * (K - 1) <= P && P <= min(RR - 1, (i + 1) * (K - 1))) recalc_block(i);
    }
    calc_answers();
}

int escape(int V1, int V2) {
    return ans[V1][V2];
}