#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]});
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());
}
static const vector<int> ZERO = {0};
auto R = [&](int i) -> const vector<int> & {
if (i < 0 || i >= N) return ZERO;
return relevant[i];
};
auto le = [&](int height, const vector<int> &r) {
return int(upper_bound(r.begin(), r.end(), height) - r.begin()) - 1;
};
auto ge = [&](int height, const vector<int> &r) {
return int(lower_bound(r.begin(), r.end(), height) - r.begin());
};
vector<vector<vector<int64>>> dp(N + 1);
for (int i = N; i >= 0; --i) {
const vector<int> &rst0 = (i != N ? R(i) : ZERO);
const vector<int> &rst1 = R(i - 1);
const vector<int> &rst2 = R(i - 2);
int s0 = rst0.size();
int s1 = rst1.size();
int s2 = rst2.size();
dp[i].assign(s1, vector<int64>(s2, 0));
if (i == N) continue;
for (int id1 = 0; id1 < s1; ++id1) {
int p1 = rst1[id1];
vector<int64> pref1(s0), pref2(s0), pref3(s0);
vector<int64> suff2(s0), suff3(s0);
for (int xi = 0; xi < s0; ++xi) {
int x = rst0[xi];
int64 base = dp[i + 1][xi][id1] + grid(i + 1, x);
pref1[xi] = base - grid(i, x);
pref2[xi] = base;
suff2[xi] = base;
if (i != 0) {
pref3[xi] = base + grid(i - 1, x);
suff3[xi] = base + 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]);
}
for (int x = s0 - 2; x >= 0; --x) {
suff2[x] = max(suff2[x], suff2[x + 1]);
suff3[x] = max(suff3[x], suff3[x + 1]);
}
int le_p1 = le(p1, rst0);
int ge_p1_1 = ge(p1 + 1, rst0);
for (int id2 = 0; id2 < s2; ++id2) {
int p2 = rst2[id2];
if (p2 > p1) continue;
int64 &cur = dp[i][id1][id2];
cur = max(cur, pref1[le_p1]);
if (p1 + 1 <= ht) {
if (i == 0) {
cur = max(cur, suff2[ge_p1_1] - grid(i, p1));
} else {
cur = max(cur, suff3[ge_p1_1] - grid(i - 1, p1) - grid(i, p1));
}
}
}
int64 val = -inf;
int ptr = ge_p1_1;
for (int id2 = 0; id2 < s2; ++id2) {
int p2 = rst2[id2];
if (p2 <= p1) continue;
while (ptr < s0 && rst0[ptr] <= p2) {
int x = rst0[ptr];
val = max(val, dp[i + 1][ptr][id1] + grid(i + 1, x));
ptr++;
}
int64 &cur = dp[i][id1][id2];
cur = max(cur, pref1[le_p1]);
cur = max(cur, val - grid(i, p1));
if (p2 + 1 <= ht) {
int ge_p2_1 = ge(p2 + 1, rst0);
if (i == 0) {
cur = max(cur, suff2[ge_p2_1] - grid(i, p1));
} else {
cur = max(cur, suff3[ge_p2_1] - grid(i - 1, p2) - grid(i, p1));
}
}
}
}
}
return dp[0][0][0];
}
