#include <bits/stdc++.h>
using namespace std;
namespace {
using int64 = long long;
const int64 inf = 1e15;
}; // namespace
int64 max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int &i : Y) {
i++;
}
const int ht = *max_element(Y.begin(), Y.end());
vector grid(N + 1, vector<int64>(ht + 1));
vector<vector<int>> at(N);
for (int i = 0; i < M; ++i) {
grid[X[i]][Y[i]] += W[i];
at[X[i]].push_back(Y[i]);
if (Y[i] + 1 <= ht) {
at[X[i]].push_back(Y[i] + 1);
}
}
for (int i = 0; i < N; ++i) {
at[i].push_back(ht);
}
for (int i = 0; i < N; ++i) {
for (int j = 1; j <= ht; ++j) {
grid[i][j] += grid[i][j - 1];
}
}
vector<vector<int>> relevant(N);
for (int i = 0; i < N; ++i) {
relevant[i] = {0};
for (int jj = -1; jj <= 1; ++jj) {
if (i + jj >= 0 && i + jj < N) {
for (int &j : at[i + jj]) {
relevant[i].push_back(j);
}
}
}
sort(relevant[i].begin(), relevant[i].end());
relevant[i].erase(unique(relevant[i].begin(), relevant[i].end()), relevant[i].end());
}
vector<vector<vector<int64>>> dp(N + 1);
auto tl = [&](int height, int i) {
vector<int> bak = {0};
vector<int> *r = i >= 0 ? &relevant[i] : &bak;
auto it = lower_bound(r->begin(), r->end(), height);
assert(it != r->end() && *it == height);
return it - r->begin();
};
auto le = [&](int height, int i) {
vector<int> bak = {0};
vector<int> *r = i >= 0 ? &relevant[i] : &bak;
return int(upper_bound(r->begin(), r->end(), height) - r->begin()) - 1;
};
auto ge = [&](int height, int i) {
vector<int> bak = {0};
vector<int> *r = i >= 0 ? &relevant[i] : &bak;
return lower_bound(r->begin(), r->end(), height) - r->begin();
};
for (int i = N; i >= 0; --i) {
vector<int> rst0 = i != N ? relevant[i] : vector<int>({0});
vector<int> rst1 = i >= 1 ? relevant[i - 1] : vector<int>({0});
vector<int> rst2 = i >= 2 ? relevant[i - 2] : vector<int>({0});
int s1 = i >= 1 ? int(rst1.size()) : 1;
int s2 = i >= 2 ? int(rst2.size()) : 1;
int s0 = rst0.size();
dp[i] = vector(s1, vector<int64>(s2));
if (i == N) {
continue;
}
for (int &p1 : rst1) {
vector<int64> pref1(s0), suff1(s0), pref2(s0), suff2(s0), pref3(s0), suff3(s0), pref4(s0), suff4(s0);
for (int &x : rst0) {
pref1[tl(x, i)] = suff1[tl(x, i)] = dp[i + 1][tl(x, i)][tl(p1, i - 1)] + grid[i + 1][x] - grid[i][x];
pref2[tl(x, i)] = suff2[tl(x, i)] = dp[i + 1][tl(x, i)][tl(p1, i - 1)] + grid[i + 1][x];
if (i != 0) {
pref3[tl(x, i)] = suff3[tl(x, i)] = dp[i + 1][tl(x, i)][tl(p1, i - 1)] + grid[i + 1][x] + grid[i - 1][x];
pref4[tl(x, i)] = suff4[tl(x, i)] = dp[i + 1][tl(x, i)][tl(p1, i - 1)] + grid[i + 1][x] - grid[i][x] + grid[i - 1][x];
}
}
for (int x = 1; x < s0; ++x) {
pref1[x] = max(pref1[x], pref1[x - 1]);
pref2[x] = max(pref2[x], pref2[x - 1]);
pref3[x] = max(pref3[x], pref3[x - 1]);
pref4[x] = max(pref4[x], pref4[x - 1]);
}
for (int x = s0 - 2; x >= 0; --x) {
suff1[x] = max(suff1[x], suff1[x + 1]);
suff2[x] = max(suff2[x], suff2[x + 1]);
suff3[x] = max(suff3[x], suff3[x + 1]);
suff4[x] = max(suff4[x], suff4[x + 1]);
}
{
for (int &p2 : rst2) {
if (p2 > p1) continue;
dp[i][tl(p1, i - 1)][tl(p2, i - 2)] = max(dp[i][tl(p1, i - 1)][tl(p2, i - 2)], pref1[le(p1, i)]);
if (i == 0) {
if (p1 + 1 <= ht) dp[i][tl(p1, i - 1)][tl(p2, i - 2)] = max(dp[i][tl(p1, i - 1)][tl(p2, i - 2)], suff2[ge(p1 + 1, i)] - grid[i][p1]);
} else {
if (p1 + 1 <= ht) dp[i][tl(p1, i - 1)][tl(p2, i - 2)] = max(dp[i][tl(p1, i - 1)][tl(p2, i - 2)], suff3[ge(p1 + 1, i)] - grid[i - 1][p1] - grid[i][p1]);
}
}
int64 val = -inf;
int ptr = ge(p1 + 1, i);
for (int &p2 : rst2) {
if (p2 <= p1) continue;
while (ptr < int(rst0.size()) && rst0[ptr] <= p2) {
val = max(val, dp[i + 1][ptr][tl(p1, i - 1)] + grid[i + 1][rst0[ptr]]);
ptr++;
}
dp[i][tl(p1, i - 1)][tl(p2, i - 2)] = max(dp[i][tl(p1, i - 1)][tl(p2, i - 2)], pref1[le(p1, i)]);
if (p2 <= ht) {
dp[i][tl(p1, i - 1)][tl(p2, i - 2)] = max(dp[i][tl(p1, i - 1)][tl(p2, i - 2)], val - grid[i][p1]);
} else {
if (p1 + 1 <= ht) dp[i][tl(p1, i - 1)][tl(p2, i - 2)] = max(dp[i][tl(p1, i - 1)][tl(p2, i - 2)], suff2[ge(p1 + 1, i)] - grid[i][p1]);
}
if (i == 0) {
if (p2 + 1 <= ht) dp[i][tl(p1, i - 1)][tl(p2, i - 2)] = max(dp[i][tl(p1, i - 1)][tl(p2, i - 2)], suff2[ge(p2 + 1, i)] - grid[i][p1]);
} else {
if (p2 + 1 <= ht) dp[i][tl(p1, i - 1)][tl(p2, i - 2)] = max(dp[i][tl(p1, i - 1)][tl(p2, i - 2)], suff3[ge(p2 + 1, i)] - grid[i - 1][p2] - grid[i][p1]);
}
}
}
}
}
return dp[0][0][0];
}
