#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
const ll infm = -1e18;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
int n = N, m = M;
for (int i = 0; i < m; i++){
X[i]++; Y[i]++;
}
vector<int> dy[n + 1];
vector<pii> d[n + 1];
for (int i = 0; i < m; i++){
d[X[i]].pb({Y[i], i});
}
vector<ll> pr[n + 1];
for (int i = 1; i <= n; i++){
sort(d[i].begin(), d[i].end());
pr[i].resize(d[i].size() + 1);
for (int j = 1; j <= d[i].size(); j++){
pr[i][j] = pr[i][j - 1] + W[d[i][j - 1].ss];
dy[i].pb(d[i][j - 1].ff);
}
dy[i].pb(n + 1);
}
vector<int> :: iterator it;
auto F = [&](int i, int j){
it = upper_bound(dy[i].begin(), dy[i].end(), j);
int t = (int) (it - dy[i].begin());
return pr[i][t];
};
vector<ll> dp[n + 1][2];
vector<int> ii[n + 1];
dp[1][0].pb(0); dp[1][1].pb(0); ii[1].pb(0);
dp[1][0].pb(0); dp[1][1].pb(0); ii[1].pb(n);
for (int i = 2; i <= n; i++){
int a = (int) dp[i - 1][0].size();
vector<ll> pr1(a + 1); pr1[0] = infm;
for (int j = 1; j <= a; j++){
pr1[j] = max(pr1[j - 1], dp[i - 1][0][j - 1] - F(i - 1, ii[i - 1][j - 1]));
}
vector<ll> pr4(a + 2);
for (int j = a; j > 0; j--){
pr4[j] = max(pr4[j + 1], max(dp[i - 1][0][j - 1], dp[i - 1][1][j - 1]) + F(i, ii[i - 1][j - 1]));
}
a = (int) dp[i - 2][0].size();
vector<ll> pr2(a + 1), pr3(a + 2);
if (i > 2){
for (int j = 1; j <= a; j++){
pr2[j] = max(pr2[j - 1], max(dp[i - 2][0][j - 1], dp[i - 2][1][j - 1]));
}
for (int j = a; j > 0; j--){
pr3[j] = max(pr3[j + 1], max(dp[i - 2][0][j - 1], dp[i - 2][1][j - 1]) + F(i - 1, ii[i - 2][j - 1]));
}
}
for (int x: dy[i]){
int j = x - 1;
ll a, b;
it = upper_bound(ii[i - 1].begin(), ii[i - 1].end(), j);
int t = (int) (it - ii[i - 1].begin());
a = pr1[t] + F(i - 1, j);
b = max(0LL, pr4[t + 1] - F(i, j));
if (i > 2){
it = upper_bound(ii[i - 2].begin(), ii[i - 2].end(), j);
int t = (int) (it - ii[i - 2].begin());
a = max({a, pr2[t] + F(i - 1, j), pr3[t + 1]});
}
dp[i][0].pb(a);
dp[i][1].pb(b);
ii[i].pb(j);
}
if (ii[i][0]){
dp[i][0].insert(dp[i][0].begin(), 0);
dp[i][1].insert(dp[i][1].begin(), 0);
ii[i].insert(ii[i].begin(), 0);
}
}
ll out = 0;
for (int i = 1; i <= n; i++){
for (ll j: dp[i][0]){
out = max(out, j);
}
for (ll j: dp[i][1]){
out = max(out, j);
}
}
return out;
}
