#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#define ref(x) (*(x))
#define prv(x) for(auto& pval : x) cout << pval << " "; cout << "\n";
#ifdef LOC
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n";
#else
#define debug(...)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
ostream& operator << (ostream& out, vector<T> v) {
out << "{ ";
for(auto& i : v) {
out << i << " ";
}
out << "} ";
return out;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
const int maxh = N + 5;
vector<vector<array<int,2>>> xpoints(N);
for(int i = 0; i < M; i++) {
xpoints[X[i]].pb({Y[i], W[i]});
}
for(auto& v : xpoints) {
sort(itr(v));
}
vector<vector<ll>> pfx(N);
vector<vector<int>> dp_idxs(N);
for(int x = 0; x < N; x++) {
if(sz(xpoints[x]) == 0 || xpoints[x][0][0] > 1) {
pfx[x].pb(0);
dp_idxs[x].pb(0);
}
for(auto& p : xpoints[x]) {
if(p[0] != 0 && (!sz(dp_idxs[x]) || dp_idxs[x].back() != p[0] - 1)) {
pfx[x].pb((sz(pfx[x]) ? pfx[x].back() : 0));
dp_idxs[x].pb(p[0] - 1);
}
if(!sz(dp_idxs[x]) || dp_idxs[x].back() != p[0]) {
pfx[x].pb((sz(pfx[x]) ? pfx[x].back() : 0) + p[1]);
dp_idxs[x].pb(p[0]);
}
}
pfx[x].pb((sz(pfx[x]) ? pfx[x].back() : 0));
dp_idxs[x].pb(maxh);
}
debug(pfx);
debug(dp_idxs);
vector<vector<ll>> inc_dp(N), dec_dp(N);
inc_dp[0].assign(sz(dp_idxs[0]), 0);
dec_dp[0].assign(sz(dp_idxs[0]), 0);
for(int x = 1; x < N; x++) {
int psz = sz(dp_idxs[x - 1]), csz = sz(dp_idxs[x]);
// calc inc_dp
inc_dp[x].assign(sz(dp_idxs[x]), 0);
ll gmx = 0; int gptr = psz - 1;
for(int i = csz - 1; i >= 0; i--) {
ll h = dp_idxs[x][i];
while(gptr >= 0 && dp_idxs[x - 1][gptr] >= h) {
ll v = max(inc_dp[x - 1][gptr], dec_dp[x - 1][gptr]);
gmx = max(gmx, v + pfx[x][i]);
gptr--;
}
inc_dp[x][i] = max(inc_dp[x][i], gmx - pfx[x][i]);
}
dec_dp[x].assign(csz, 0);
ll smx = 0; int sptr = 0;
for(int i = 0; i < csz; i++) {
ll h = dp_idxs[x][i];
while(sptr < psz && dp_idxs[x - 1][sptr] < h) {
ll v = dec_dp[x - 1][sptr];
smx = max(smx, v - pfx[x - 1][sptr]);
sptr++;
}
dec_dp[x][i] = max(dec_dp[x][i], smx + pfx[x - 1][sptr]);
}
if(x == 1) {
continue;
}
int ppsz = sz(dp_idxs[x - 2]);
int gpptr = ppsz - 1; gptr = psz - 1;
ll gppmx = 0, gvmx = 0;
for(int i = csz - 1; i >= 0; i--) {
ll h = dp_idxs[x][i];
while(gptr >= 0 && dp_idxs[x - 1][gptr] >= h) {
while(gpptr >= 0 && dp_idxs[x - 2][gpptr] >= dp_idxs[x - 1][gptr]) {
gppmx = max(gppmx, dec_dp[x - 2][gpptr]);
gppmx = max(gppmx, inc_dp[x - 2][gpptr]);
gpptr--;
}
gvmx = max(gvmx, pfx[x - 1][gptr] + gppmx);
gptr--;
}
dec_dp[x][i] = max(dec_dp[x][i], gvmx);
}
}
debug(inc_dp);
debug(dec_dp);
ll ans = 0;
for(auto& p : inc_dp[N - 1]) {
ans = max(ans, p);
}
for(auto& p : dec_dp[N - 1]) {
ans = max(ans, p);
}
return ans;
}
