#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<vector<pi>> occ(n + 1);
for (int i = 0; i < m; ++i) {
occ[x[i]].push_back({y[i], w[i]});
}
for (int i = 0; i < n; ++i) occ[i].push_back({n, 0});
for (int i = 0; i < n; ++i) sort(occ[i].begin(), occ[i].end());
vector<vector<ll>> pref(n + 1);
for (int i = 0; i < n; ++i) {
pref[i].assign(occ[i].size(), 0);
pref[i][0] = occ[i][0].S;
for (int j = 1; j < occ[i].size(); ++j) pref[i][j] = pref[i][j - 1] + occ[i][j].S;
}
auto under = [&](int x, int r) {
int low = 0, high = occ[x].size() - 1, sol = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (occ[x][mid].F <= r) {
sol = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (sol == -1) return 0LL;
return pref[x][sol];
};
auto between = [&](int x, int l, int r) {
return under(x, r) - under(x, l - 1);
};
vector<vector<ll>> dp0(n + 1), dp1(n + 1);
for (int i = 0; i < n; ++i) dp0[i].assign(occ[i].size(), 0);
for (int i = 0; i < n; ++i) dp1[i].assign(occ[i].size(), 0);
for (int i = 1; i < n; ++i) {
// p[i] < p[i - 1]
int ptr = occ[i - 1].size() - 1;
ll mx = 0;
for (int j = occ[i].size() - 1; j >= 0; --j) {
while (ptr >= 0 && occ[i - 1][ptr].F - 1 >= occ[i][j].F) {
ckmax(mx, max(dp0[i - 1][ptr], dp1[i - 1][ptr]) + under(i, occ[i - 1][ptr].F - 1));
--ptr;
}
ckmax(dp0[i][j], mx - under(i, occ[i][j].F - 1));
}
// p[i] > p[i - 1]
vector<ll> pref, suff;
if (i >= 2) {
pref.assign(occ[i - 2].size() + 1, -1e18);
suff.assign(occ[i - 2].size() + 1, -1e18);
pref[0] = max(dp0[i - 2][0], dp1[i - 2][0]);
for (int j = 1; j < occ[i - 2].size(); ++j) {
pref[j] = max(pref[j - 1], max(dp0[i - 2][j], dp1[i - 2][j]));
}
for (int j = occ[i - 2].size() - 1; j >= 0; --j) {
suff[j] = max(suff[j + 1], max(dp0[i - 2][j], dp1[i - 2][j]) + under(i - 1, occ[i - 2][j].F - 1));
}
}
ptr = 0;
mx = -1e18;
for (int j = 0; j < occ[i].size(); ++j) {
while (ptr < occ[i - 1].size() && occ[i - 1][ptr].F <= occ[i][j].F) {
ckmax(mx, dp1[i - 1][ptr] - under(i - 1, occ[i - 1][ptr].F - 1));
++ptr;
}
ckmax(dp1[i][j], mx + under(i - 1, occ[i][j].F - 1));
if (i >= 2) {
int low = 0, high = occ[i - 2].size() - 1, sol = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (occ[i - 2][mid].F <= occ[i][j].F) {
sol = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (sol != -1) {
ckmax(dp1[i][j], under(i - 1, occ[i][j].F - 1) + pref[sol]);
}
ckmax(dp1[i][j], suff[sol + 1]);
}
}
}
ll ans = 0;
for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp0[n - 1][i]);
for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp1[n - 1][i]);
return ans;
}
