#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,X[300009],Y[300009],W[300009],DP0[300009],DP1[300009],best[300009],pas;
vector <pair <long long, long long> > dp0[300009],dp1[300009],pr[300009];
long long max_weights(int NN, int MM, std::vector<int> XX, std::vector<int> YY, std::vector<int> WW) {
a=NN;b=MM;
for(i=0; i<b; i++){
XX[i]++;YY[i]++;
X[i+1]=XX[i];Y[i+1]=YY[i];W[i+1]=WW[i];
}
for(i=1; i<=b; i++){
//if(Y[i]!=1){
dp0[X[i]].push_back({Y[i]-1,0});
dp1[X[i]].push_back({Y[i]-1,0});
//}
pr[X[i]].push_back({Y[i],W[i]});
}
for(i=0; i<=a; i++){
if(i!=0){
dp0[i].push_back({a+4,0});
dp1[i].push_back({a+4,0});
}
/*dp0[i].push_back({0,0});
dp1[i].push_back({0,0});*/
pr[i].push_back({0,0});
}
for(i=0; i<=a; i++){
sort(dp0[i].begin(),dp0[i].end());
sort(dp1[i].begin(),dp1[i].end());
sort(pr[i].begin(),pr[i].end());
for(j=1; j<pr[i].size(); j++){
pr[i][j].second+=pr[i][j-1].second;
}
}
//return max(pr[1].back().second,pr[2].back().second);
for(i=1; i<=a+1; i++){
//DP0[i-1] DP1[i-1] best[i-1]
DP0[i-1]=-N;
DP1[i-1]=-N;
for(j=0; j<dp0[i-1].size(); j++){
best[i-1]=max(best[i-1],dp0[i-1][j].second);
}
if(i==a+1) break;
ii=0;
for(j=0; j<dp0[i-1].size(); j++){
while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i-1][j].first) ii++;
DP0[i-1]=max(DP0[i-1],dp0[i-1][j].second+pr[i][ii].second);
}
ii=0;
for(j=0; j<dp1[i-1].size(); j++){
while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i-1][j].first) ii++;
DP1[i-1]=max(DP1[i-1],dp1[i-1][j].second-pr[i-1][ii].second);
}
//dp1[i]
ii=0;
for(j=0; j<dp1[i].size(); j++){
while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i][j].first) ii++;
dp1[i][j].second=pr[i-1][ii].second+DP1[i-1];
dp1[i][j].second=max(dp1[i][j].second,best[i-1]);
}
//dp0[i]
ii=0;
for(j=0; j<dp0[i].size(); j++){
dp0[i][j].second=dp1[i][j].second;
while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i][j].first) ii++;
zx=-pr[i][ii].second+DP0[i-1];
dp0[i][j].second=max(dp0[i][j].second,zx);
}
}
for(i=1; i<=a; i++){
pas=max(pas,best[i]);
}
return pas;
}
