#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>
#ifndef EVAL
#include <iostream>
#endif
#include "wombats.h"
#define entire(a) std::begin((a)), std::end((a))
const int64_t INF = 2'000'000'000'000;
struct Matrix {
int64_t a1 = 0, a2 = INF, b1 = INF, b2 = 0;
Matrix operator*(const Matrix &rhs) const {
return {
.a1 = std::min(a1 + rhs.a1, b1 + rhs.a2),
.a2 = std::min(b2 + rhs.a2, a2 + rhs.a1),
.b1 = std::min(a1 + rhs.b1, b1 + rhs.b2),
.b2 = std::min(b2 + rhs.b2, a2 + rhs.b1),
};
}
};
template <typename T>
struct SegmentTree {
std::vector<T> values;
int offset;
SegmentTree() : values(), offset() {}
explicit SegmentTree(int sz) : values(2 * sz), offset(sz) {}
void update(int i, T value) {
i += offset;
values[i] = value;
propagate(i);
}
void propagate(int i) {
while (i /= 2) values[i] = values[2 * i] * values[2 * i + 1];
}
T query(int l, int r) {
l += offset;
r += offset;
T left, right;
while (l < r) {
if (l & 1) left = left * values[l++];
if (r & 1) right = values[--r] * right;
l >>= 1;
r >>= 1;
}
return left * right;
}
};
std::vector<std::vector<int>> h, v;
int r, c;
SegmentTree<Matrix> st;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
h.reserve(R);
v.reserve(R);
for (int i = 0; i < R; i++) {
h.emplace_back(entire(H[i]));
v.emplace_back(entire(V[i]));
}
r = R;
c = C;
int o = 1;
while (o < 2 * R) o *= 2;
st = SegmentTree<Matrix>(o);
for (int i = 0; i < R; i++) {
st.update(2 * i, {
.a2 = H[i][0],
.b1 = H[i][0],
});
if (i + 1 < R) {
st.update(2 * i + 1, {
.a1 = V[i][0],
.b2 = V[i][1],
});
}
}
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
st.update(2 * P, {
.a2 = h[P][0],
.b1 = h[P][0],
});
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
st.update(2 * P + 1, {
.a1 = v[P][0],
.b2 = v[P][1],
});
}
int escape(int V1, int V2) {
if (c == 2) {
auto res = st.query(0, 2 * r);
if (V1 == 0 && V2 == 0)
return res.a1;
else if (V1 == 0 && V2 == 1)
return res.b1;
else if (V1 == 1 && V2 == 0)
return res.a2;
else if (V1 == 1 && V2 == 1)
return res.b2;
} else {
std::vector<int> dist(c, 0);
dist[V1] = 0;
for (int i = V1 + 1; i < c; i++) {
dist[i] = dist[i - 1] + h[0][i - 1];
}
for (int i = V1 - 1; i >= 0; i--) {
dist[i] = dist[i + 1] + h[0][i];
}
std::priority_queue<std::pair<int, int>> pq;
for (int i = 0; i + 1 < r; i++) {
// phase 1: process vertical segments
for (int j = 0; j < c; j++) {
dist[j] += v[i][j];
}
// phase 2: process horizontal segments
while (!pq.empty()) pq.pop(); // whyy is there no pq.clear();
for (int j = 0; j < c; j++) {
pq.push({-dist[j], j});
}
while (!pq.empty()) {
auto [d, j] = pq.top();
pq.pop();
d = -d;
if (d > dist[j]) continue;
if (j > 0 && dist[j - 1] > d + h[i + 1][j - 1]) {
dist[j - 1] = d + h[i + 1][j - 1];
pq.push({-dist[j - 1], j - 1});
}
if (j + 1 < c && dist[j + 1] > d + h[i + 1][j]) {
dist[j + 1] = d + h[i + 1][j];
pq.push({-dist[j + 1], j + 1});
}
}
}
return dist[V2];
}
}
