#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
using lint=long long;
const int lim=1e5+100;
using pii=pair<int,lint>;
int n,m;
vector<int>inds[lim];
vector<lint> dp[lim],up[lim];
vector<pii>pref[lim];
lint p(int i,int r){
if(n<=i)return 0;
auto rp=lower_bound(pref[i].begin(),pref[i].end(),pii{r+1,0});
rp--;
return rp->second;
}
lint max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W) {
n=N,m=M;
for(int i=0;i<m;i++){
pref[X[i]].push_back({Y[i]+1,W[i]});
}
for(int i=0;i<n;i++){
pref[i].push_back({0,0});
pref[i].push_back({n+6,0});
sort(pref[i].begin(),pref[i].end());
for(int j=0;j<size(pref[i]);j++){
if(pref[i][j].first)inds[i].push_back(pref[i][j].first-1);
else inds[i].push_back(0);
}
for(int j=1;j<size(pref[i]);j++){
pref[i][j].second+=pref[i][j-1].second;
}
}
dp[0].resize(inds[0].size());
up[0].resize(inds[0].size());
for(int i=0;i<size(dp[0]);i++){
dp[0][i]=p(1,inds[0][i]);
up[0][i]=0;
}
for(int i=1;i<n;i++){
dp[i].resize(inds[i].size());
up[i].resize(inds[i].size());
lint max1=0;
int pp=0;
for(int j=0;j<size(dp[i]);j++){
while(pp<size(up[i-1])&&inds[i-1][pp]<=inds[i][j]){
max1=max(max1,up[i-1][pp]-p(i-1,inds[i-1][pp]));
pp++;
}
dp[i][j]=max(dp[i][j],max1+p(i-1,inds[i][j])+p(i+1,inds[i][j]));
up[i][j]=max(up[i][j],max1+p(i-1,inds[i][j]));
auto p=upper_bound(inds[i-1].begin(),inds[i-1].end(),inds[i][j]);
if(p!=inds[i-1].begin()){
p--;
up[i][j]=max(up[i][j],dp[i-1][p-inds[i-1].begin()]);
}
}
max1=0;
pp=size(up[i-1]);
pp--;
for(int j=int(size(dp[i]))-1;0<=j;j--){
while(0<=pp&&inds[i][j]<=inds[i-1][pp]){
max1=max(max1,dp[i-1][pp]);
pp--;
}
dp[i][j]=max(dp[i][j],max1-p(i,inds[i][j])+p(i+1,inds[i][j]));
}
/*
cerr<<i<<" {\n";
for(int j=0;j<dp[i].size();j++){
cerr<<" "<<inds[i][j]<<" :: "<<dp[i][j]<<"\n";
}cerr<<"}{\n";
for(int j=0;j<dp[i].size();j++){
cerr<<" "<<inds[i][j]<<" :: "<<up[i][j]<<"\n";
}cerr<<"}\n";
*/
}
lint ans=0;
for(int i=0;i<size(dp[n-1]);i++){
ans=max(ans,dp[n-1][i]);
}
return ans;
}
