#include <bits/stdc++.h>
#include "fish.h"
#define ll long long
#define vc vector
using namespace std;
ll max_weights(int N, int M, vc<int> X, vc<int> Y, vc<int> W) {
vc<ll> ind(M); for(ll i=0;i<M;++i) ind[i]=i;
sort(ind.begin(),ind.end(),[&](ll a,ll b){return Y[a]<Y[b];});
vc<vc<pair<ll, ll>>> f(N);
vc<vc<ll>> rel(N, vc<ll>(1, -1)), dpm(N, vc<ll>(1, 0)), dpv(N, vc<ll>(1, 0)), dpn(N, vc<ll>(1, 0));
for(auto i: ind){
f[X[i]].emplace_back(Y[i], W[i]);
if(X[i]-1>=0) rel[X[i]-1].push_back(Y[i]),dpn[X[i]-1].push_back(0),dpm[X[i]-1].push_back(0),dpv[X[i]-1].push_back(0);
if(X[i]+1<N) rel[X[i]+1].push_back(Y[i]),dpn[X[i]+1].push_back(0),dpm[X[i]+1].push_back(0),dpv[X[i]+1].push_back(0);
}
for(ll i=0;i<N;++i){
if(i-2>=0){
for(ll j=0, prej=0, c=0, pp=0, mm=0;j<(ll)rel[i].size();++j){
while(pp<(ll)rel[i-2].size()&&rel[i-2][pp]<=rel[i][j])mm=max(mm, max(dpv[i-2][pp], dpm[i-2][pp])),++pp;
while(prej<(ll)f[i-1].size()&&f[i-1][prej].first<=rel[i][j])c+=f[i-1][prej++].second;
dpv[i][j]=max(dpv[i][j],mm+c);
dpm[i][j]=max(dpm[i][j],mm+c);
}
for(ll j=(ll)rel[i].size()-1, pp=(ll)rel[i-2].size(), mm=0;j>=0;--j){
while(pp-1>=0&&rel[i-2][pp-1]>=rel[i][j])mm=max(mm, dpn[i-2][--pp]);
dpv[i][j]=max(dpv[i][j],mm);
dpm[i][j]=max(dpm[i][j],mm);
}
}
if(i-1>=0){
for(ll j=0, prej=0, pf=0, mm=0;j<(ll)rel[i].size();++j){
while(1){
if(prej<(ll)rel[i-1].size()&&rel[i-1][prej]<=rel[i][j]&&(!(pf<(ll)f[i-1].size()) || rel[i-1][prej]<f[i-1][pf].first))mm=max(mm, dpm[i-1][prej++]);
else if(pf<(ll)f[i-1].size()&&f[i-1][pf].first<=rel[i][j])mm+=f[i-1][pf++].second;
else break;
}
dpm[i][j]=max(dpm[i][j], mm);
}
ll mm=0;
for(auto v: dpn[i-1])mm=max(mm, v);
for(ll j=0, nas=0, c=0;j<(ll)rel[i].size();++j){
while(nas<(ll)f[i].size()&&f[i][nas].first<=rel[i][j])c+=f[i][nas++].second;
dpv[i][j]=max({dpv[i][j],dpm[i][j], mm-c});
}
}
if(i+1<N){
for(ll j=0, nas=0, c=0;j<(ll)rel[i].size();++j){
while(nas<(ll)f[i+1].size()&&f[i+1][nas].first<=rel[i][j])c+=f[i+1][nas++].second;
dpn[i][j]=max(dpn[i][j],max(dpv[i][j], dpm[i][j])+c);
}
}
}
ll ans=0;
for(ll i=0;i<N;++i){
for(ll j=0;j<(ll)rel[i].size();++j)ans=max({ans, dpn[i][j], dpv[i][j], dpm[i][j]});
}
return ans;
}
