#include "wombats.h"

#include <bits/stdc++.h>

constexpr int inf = 1e9 + 1;
int n, m;

struct Cum {
    std::vector<int> L;
    std::vector<std::vector<int>> data;

    std::vector<std::vector<int>> v, h;
    int len;

    Cum() {
        len = 0;
    }
    Cum(std::vector<int> v, std::vector<int> h) {
        len = 1;
        L = v;
        this->v.push_back(v);
        this->h.push_back(h);
        return;

        assert(v.size() == m);
        assert(h.size() == m - 1);
        std::vector<int> ph(m);
        std::partial_sum(h.begin(), h.end(), ph.begin() + 1);
        data.assign(m, std::vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                data[i][j] = abs(ph[i] - ph[j]);
            }
        }
    }
};

Cum fuck(Cum a) {
    if (a.len == -1) {
        return a;
    }
    int l = a.len;
    Cum res;
    res.len = -1;
    res.data.resize(m);
    for (int i = 0; i < m; i++) {
        std::vector<int> dp(m, inf);
        dp[i] = 0;
        auto shit = [&](auto& h) {
            for (int j = 1; j < m; j++) {
                dp[j] = std::min(dp[j], dp[j - 1] + h[j - 1]);
            }
            for (int j = m - 2; j >= 0; j--) {
                dp[j] = std::min(dp[j], dp[j + 1] + h[j]);
            }
        };
        shit(a.h[0]);
        for (int j = 1; j < l; j++) {
            for (int t = 0; t < m; t++) {
                dp[t] += a.v[j][t];
            }
            shit(a.h[j]);
        }
        res.data[i] = dp;
    }
    return res;
}

Cum merge(Cum a, Cum b) {
    if (!a.len || !b.len) {
        return a.len ? a : b;
    }
    if (a.len == -1 || b.len == -1) {
        if (a.len != -1) {
            a = fuck(a);
        }
        if (b.len != -1) {
            b = fuck(b);
        }
    } else {
        a.L = b.L;
        a.len += b.len;
        a.v.insert(a.v.end(), b.v.begin(), b.v.end());
        a.h.insert(a.h.end(), b.h.begin(), b.h.end());
        if (a.len > 100) {
            a = fuck(a);
        }
        return a;
    }
    Cum res;
    res.L = a.L;
    res.data.assign(m, std::vector<int>(m, inf));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            for (int t = 0; t < m; t++) {
                res.data[i][t] = std::min(res.data[i][t], a.data[i][j] + b.L[j] + b.data[j][t]);
            }
        }
    }
    return res;
}

std::vector<std::vector<int>> h, v;

int size;
std::vector<Cum> data;

void build() {
    for (size = 1; size < n; size *= 2)
        ;
    data.resize(2 * size);
    for (int i = 0; i < n; i++) {
        data[size + i] = Cum(v[i], h[i]);
    }
    for (int i = size - 1; i > 0; i--) {
        data[i] = merge(data[2 * i], data[2 * i + 1]);
    }
}

void update(int i) {
    data[i + size] = Cum(v[i], h[i]);
    i += size;
    for (i >>= 1; i > 0; i >>= 1) {
        data[i] = merge(data[2 * i], data[2 * i + 1]);
    }
}

void init(int r, int c, int H[5000][200], int V[5000][200]) {
    n = r;
    m = c;
    h.assign(n, std::vector<int>(m - 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 1; j++) {
            h[i][j] = H[i][j];
        }
    }
    v.assign(n, std::vector<int>(m));
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            v[i + 1][j] = V[i][j];
        }
    }
    build();
}

void changeH(int p, int q, int w) {
    h[p][q] = w;
    update(p);
}

void changeV(int p, int q, int w) {
    v[p + 1][q] = w;
    update(p + 1);
}

int escape(int v1, int v2) {
    if (data[1].len != -1) {
        data[1] = fuck(data[1]);
    }

    int res = data[1].data[v1][v2];
    return res;
    // return 42;
}