#include <iostream>
#include <vector>
#include <algorithm>
#include <cstddef>
using namespace std;
const long long X = 1e18;
struct E {
int t;
long long c;
int r;
};
vector<vector<E>> a;
vector<int> l;
vector<size_t> it;
vector<pair<int, int>> s;
vector<int> v;
void ae(int u, int t, long long c) {
a[u].push_back({t, c, (int)a[t].size()});
a[t].push_back({u, 0, (int)a[u].size() - 1});
}
bool b(int s, int t) {
l.assign(a.size(), -1);
vector<int> q;
q.push_back(s);
l[s] = 0;
size_t h = 0;
while (h < q.size()) {
int u = q[h++];
for (auto& e : a[u]) {
if (e.c > 0 && l[e.t] < 0) {
l[e.t] = l[u] + 1;
q.push_back(e.t);
}
}
}
return l[t] != -1;
}
long long d(int u, int t, long long f) {
if (u == t) return f;
for (size_t& i = it[u]; i < a[u].size(); ++i) {
E& e = a[u][i];
if (e.c > 0 && l[u] < l[e.t]) {
long long x = d(e.t, t, min(f, e.c));
if (x > 0) {
e.c -= x;
a[e.t][e.r].c += x;
return x;
}
}
}
return 0;
}
long long mf(int s, int t) {
long long f = 0;
while (b(s, t)) {
it.assign(a.size(), 0);
long long x;
while ((x = d(s, t, X)) > 0) f += x;
}
return f;
}
int bst(int l, int r, int& ni, int b) {
int u = ni++;
s.emplace_back(-1, -1);
if (l == r) {
ae(u, v[l], X);
} else {
int m = l + (r - l) / 2;
int c1 = bst(l, m, ni, b);
int c2 = bst(m + 1, r, ni, b);
s[u - b] = {c1, c2};
ae(u, c1, X);
ae(u, c2, X);
}
return u;
}
void qst(int ni, int b, int l, int r, int ql, int qr, int u) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
ae(u, ni, X);
return;
}
int m = l + (r - l) / 2;
auto c = s[ni - b];
if (c.first != -1) {
qst(c.first, b, l, m, ql, qr, u);
qst(c.second, b, m + 1, r, ql, qr, u);
}
}
long long sp(int m, int n, const vector<long long>& c1, const vector<long long>& c2, int p) {
vector<long long> x1, x2;
vector<int> i1, i2;
for (int i = 1 - n; i <= m - 1; ++i) {
if (abs(i % 2) == p) {
i1.push_back(i);
x1.push_back(c1[i + n - 1]);
}
}
for (int j = 0; j <= m + n - 2; ++j) {
if (j % 2 == p) {
i2.push_back(j);
x2.push_back(c2[j]);
}
}
if (x1.empty() || x2.empty()) return 0;
size_t u = x1.size();
size_t v_ = x2.size();
size_t s_ = 4 * v_;
size_t tot = 2 + u + v_ + s_;
a.assign(tot, vector<E>());
const int S = 0, T = 1;
vector<int> uu(u);
v.assign(v_, 0);
int ni = 2;
for (size_t i = 0; i < u; ++i) uu[i] = ni++;
for (size_t i = 0; i < v_; ++i) v[i] = ni++;
for (size_t i = 0; i < u; ++i) ae(S, uu[i], x1[i]);
for (size_t i = 0; i < v_; ++i) ae(v[i], T, x2[i]);
s.clear();
int b = ni;
int rt = bst(0, v_ - 1, ni, b);
for (size_t i = 0; i < u; ++i) {
int l = i1[i] + n - 1;
int lo = max(0, l - m + 1);
int hi = min(l, n - 1);
qst(rt, b, 0, v_ - 1, lo, hi, uu[i]);
}
return mf(S, T);
}
