#pragma GCC optimize("Ofast,unroll-all-loops")
#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 ggrid(N + 1, vector<pair<int, int64>>());
vector<vector<int>> at(N);
for (int i = 0; i < M; ++i) {
ggrid[X[i]].push_back({Y[i], W[i]});
// ggrid[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);
ggrid[i].push_back({0, 0});
ggrid[i].push_back({1, 0});
ggrid[i].push_back({ht, 0});
}
for (int i = 0; i < N; ++i) {
if (ggrid[i].size() == 1) {
continue;
}
sort(ggrid[i].begin(), ggrid[i].end());
{
vector<pair<int, int64>> rep;
for (auto &[a, b] : ggrid[i]) {
if (!rep.empty() && rep.back().first == a) {
rep.back().second += b;
} else {
rep.push_back({a, b});
}
}
ggrid[i] = rep;
}
for (auto it = next(ggrid[i].begin()); it != ggrid[i].end(); ++it) {
it->second += prev(it)->second;
}
}
auto grid = [&](int i, int j) -> int64 {
pair<int, int64> p = {j, inf};
auto it = upper_bound(ggrid[i].begin(), ggrid[i].end(), p);
if (it == ggrid[i].begin()) {
return 0;
}
return prev(it)->second;
};
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];
}
