#include<bits/stdc++.h>
#include "fish.h"
using namespace std;
const long long N=999999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,M,ANS;
vector <pair <long long, long long> > fish[100009],JM[100009];
vector <long long> v[100009],dp[100009],dp2[100009],jm[100009],f[100009];
long long max_weights(int NN, int MM, std::vector<int> XX, std::vector<int> YY, std::vector<int> WW) {
a=NN;M=MM;
for(i=1; i<=M; i++){
fish[XX[i-1]+1].push_back({YY[i-1]+1,WW[i-1]});
}
for(i=1; i<=a; i++){
fish[i].push_back({0,0});
sort(fish[i].begin(),fish[i].end());
}
for(i=1; i<=a; i++){
v[i].push_back(0);
for(j=0; j<fish[i-1].size(); j++){
v[i].push_back(fish[i-1][j].first);
}
for(j=0; j<fish[i+1].size(); j++){
v[i].push_back(fish[i+1][j].first);
}
sort(v[i].begin(),v[i].end());
dp[i].resize(v[i].size());dp2[i].resize(v[i].size());
jm[i].resize(v[i].size());f[i].resize(v[i].size());
/*zx=0;
for(j=0; j<v[i].size(); j++){
zx+=v[i][j];
jm[i][j]=zx;
}*/
JM[i].resize(fish[i].size());
zx=0;
for(j=0; j<JM[i].size(); j++){
zx+=fish[i][j].second;
JM[i][j]={fish[i][j].first,zx};
}
for(j=0; j<v[i].size(); j++){
c=lower_bound(JM[i].begin(),JM[i].end(),make_pair(v[i][j]+1,0LL))-JM[i].begin();c--;
if(c<0) continue;
jm[i][j]=JM[i][c].second;
}
}
/*for(i=1; i<=a; i++){
cout<<i<<":\n";
for(j=0; j<v[i].size(); j++){
cout<<v[i][j]<<" "<<jm[i][j]<<"\n";
}
}*/
for(i=2; i<=a; i++){
zx=-N;
for(j=0; j<v[i-1].size(); j++){
zx=max(zx,dp[i-1][j]);
f[i-1][j]=zx;
}
for(j=0; j<v[i].size(); j++){
c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();c--;
dp2[i][j]=max(dp2[i][j],f[i-1][c]);
}
zx=-N;
for(j=0; j<v[i-1].size(); j++){
zx=max(zx,dp2[i-1][j]-jm[i-1][j]);
f[i-1][j]=zx;
}
for(j=0; j<v[i].size(); j++){
c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();c--;
d=lower_bound(JM[i-1].begin(),JM[i-1].end(),make_pair(v[i][j]+1,0LL))-JM[i-1].begin();d--;
dp2[i][j]=max(dp2[i][j],f[i-1][c]+/*jm[i-1][c]*/JM[i-1][d].second);
}
zx=-N;e=v[i-1].size();
for(j=e-1; j>=0; j--){
zx=max(zx,max(dp[i-1][j],dp2[i-1][j]));
f[i-1][j]=zx;
}
for(j=0; j<v[i].size(); j++){
c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();
if(c>=v[i-1].size()) continue;
dp2[i][j]=max(dp2[i][j],f[i-1][c]);
}
//
//
zx=-N;
for(j=0; j<v[i-1].size(); j++){
zx=max(zx,dp[i-1][j]);
f[i-1][j]=zx;
}
for(j=0; j<v[i].size(); j++){
c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();c--;
dp2[i][j]=max(dp2[i][j],f[i-1][c]);
}
zx=-N;
for(j=0; j<v[i-1].size(); j++){
zx=max(zx,dp2[i-1][j]-jm[i-1][j]);
f[i-1][j]=zx;
}
for(j=0; j<v[i].size(); j++){
c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();c--;
d=lower_bound(JM[i-1].begin(),JM[i-1].end(),make_pair(v[i][j]+1,0LL))-JM[i-1].begin();d--;
dp2[i][j]=max(dp2[i][j],f[i-1][c]+/*jm[i-1][c]*/JM[i-1][d].second);
}
zx=-N;e=v[i-1].size();
for(j=e-1; j>=0; j--){
/*c=lower_bound(v[i].begin(),v[i].end(),v[i-1][j]+1)-v[i].begin();c--;
xc=jm[i][c];*/
d=lower_bound(JM[i].begin(),JM[i].end(),make_pair(v[i-1][j]+1,0LL))-JM[i].begin();d--;
xc=JM[i][d].second;
zx=max(zx,max(dp[i-1][j],dp2[i-1][j])+xc);
f[i-1][j]=zx;
}
for(j=0; j<v[i].size(); j++){
c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();
if(c>=v[i-1].size()) continue;
dp[i][j]=max(dp[i][j],f[i-1][c]-jm[i][j]);
}
}
ANS=-N;
for(i=1; i<=a; i++){
for(j=0; j<dp[i].size(); j++){
ANS=max(ANS,dp[i][j]);
ANS=max(ANS,dp2[i][j]);
}
}
return ANS;
}
