#include <bits/stdc++.h>
#define r first
#define w second
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
const int MN=1e5+2;
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
vector<vector<pii>> fish(N+2);
for(int i=0;i<M;++i) fish[X[i]+1].push_back({Y[i]+1,(ll)W[i]});
fish[0].push_back({0,0LL});
fish[N+1].push_back({0,0LL});
for(int i=1;i<=N;++i) {
fish[i].push_back({0,0LL});
sort(fish[i].begin(),fish[i].end());
for(int j=1;j<(int)fish[i].size();++j) fish[i][j].w+=fish[i][j-1].w;
}
auto pfx=[&](int c,int r) {
return (--upper_bound(fish[c].begin(),fish[c].end(),pii(r,LLONG_MAX)))->w;
};
vector<vector<int>> stops(N+2);
stops[0].push_back(0);
stops[N+1].push_back(0);
for(int i=1;i<=N;++i) {
for(pii f:fish[i-1]) stops[i].push_back(f.r);
for(pii f:fish[i+1]) stops[i].push_back(f.r);
sort(stops[i].begin(),stops[i].end());
stops[i].erase(unique(stops[i].begin(),stops[i].end()),stops[i].end());
}
vector<ll> dp[2];
dp[0]={0LL};
dp[1]={0LL};
for(int i=1;i<=N+1;++i) {
vector<ll> ndp[2];
ll pf=0,sf=0;
int pfi=0,sfi=(int)stops[i-1].size()-1;
for(int s=0;s<(int)stops[i].size();++s) {
while(pfi<(int)stops[i-1].size()&&stops[i-1][pfi]<=stops[i][s]) {
pf=max(pf,dp[0][pfi]-pfx(i-1,stops[i-1][pfi]));
++pfi;
}
ndp[0].push_back(max(dp[1][0],pf+pfx(i-1,stops[i][s])));
}
for(int s=(int)stops[i].size()-1;s>=0;--s) {
while(sfi>=0&&stops[i-1][sfi]>=stops[i][s]) {
sf=max(sf,max(dp[0][sfi],dp[1][sfi])+pfx(i,stops[i-1][sfi]));
--sfi;
}
ndp[1].push_back(sf-pfx(i,stops[i][s]));
}
reverse(ndp[1].begin(),ndp[1].end());
dp[0].clear();
dp[1].clear();
for(ll x:ndp[0]) dp[0].push_back(x);
for(ll x:ndp[1]) dp[1].push_back(x);
}
return max(dp[0][0],dp[1][0]);
}
