#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const ll INF = 1e18;
ll max_weights(int n, int m, vi x, vi y, vi w) {
vector<vector<pair<int, ll>>> s(n + 1);
for (int i = 0; i < m; i++)
s[x[i] + 1].push_back({y[i] + 1, w[i]});
for (int i = 0; i <= n; i++) {
s[i].push_back({0, 0});
s[i].push_back({n + 1, 0});
sort(s[i].begin(), s[i].end());
ll x = 0;
for (auto &[j, w] : s[i]) {
x += w;
w = x;
}
}
vector<vi> p(n + 1);
auto pos = [&](int i, int k) {
return lower_bound(p[i].begin(), p[i].end(), k) - p[i].begin();
};
auto sum = [&](int i, int k) {
return s[i][upper_bound(s[i].begin(), s[i].end(), make_pair(k, (ll) 0)) - s[i].begin() - 1].second;
};
vector<vector<array<ll, 2>>> f(n + 1);
p[0].push_back(0);
f[0].assign(1, {-INF, -INF});
f[0][0][0] = f[0][0][1] = 0;
for (int i = 1; i <= n; i++) {
for (auto [j, w] : s[i - 1])
p[i].push_back(j);
for (auto [j, w] : s[i])
p[i].push_back(j);
sort(p[i].begin(), p[i].end());
p[i].erase(unique(p[i].begin(), p[i].end()), p[i].end());
int m = p[i].size();
f[i].assign(m + 1, {-INF, -INF});
vector<ll> a(m + 1, -INF), b(m + 1, -INF), c(m + 1, -INF), d(m + 1, -INF);
for (int k = 0; k < (int) p[i - 1].size(); k++) {
a[pos(i, p[i - 1][k])] = max(f[i - 1][k][0], f[i - 1][k][1]) + sum(i, p[i - 1][k]);
d[pos(i, p[i - 1][k])] = f[i - 1][k][1] - sum(i - 1, p[i - 1][k]);
}
if (i > 1)
for (int k = 0; k < (int) p[i - 2].size(); k++) {
b[pos(i, p[i - 2][k])] = max(f[i - 2][k][0], f[i - 2][k][1]);
c[pos(i, p[i - 2][k])] = max(f[i - 2][k][0], f[i - 2][k][1]) + sum(i - 1, p[i - 2][k]);
}
for (int k = m - 1; k >= 0; k--) {
a[k] = max(a[k], a[k + 1]);
c[k] = max(c[k], c[k + 1]);
}
for (int k = 0; k < m; k++) {
b[k + 1] = max(b[k + 1], b[k]);
d[k + 1] = max(d[k + 1], d[k]);
}
for (int k = 0; k <= m; k++) {
f[i][k][0] = max(f[i][k][0], a[k] - sum(i, p[i][k]));
f[i][k][1] = max(f[i][k][1], d[k] + sum(i - 1, p[i][k]));
if (i > 1) {
f[i][k][1] = max(f[i][k][1], b[k] + sum(i - 1, p[i][k]));
f[i][k][1] = max(f[i][k][1], c[k]);
}
f[i][k][0] = max(f[i][k][0], f[i][k][1]);
}
}
ll ans = 0;
for (auto v : f[n]) {
ans = max(ans, v[0]);
ans = max(ans, v[1]);
}
return ans;
}
