#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAX_TAILLE=100*1000+5,MAX_BON=500*1000+5,INFINI=(ll)1000*1000*1000*1000*1000*10;
ll taille,nbBonus;
ll posBon[MAX_BON][2];
vector<tuple<ll,ll,ll>> bonSurCol[MAX_TAILLE];
ll memo[MAX_BON][3];
ll premSous(ll col,ll lig) {
ll deb=0,mid,fin=bonSurCol[col].size()-1;
while (deb!=fin) {
mid=(deb+fin+1)/2;
if (get<0>(bonSurCol[col][mid])<=lig) {
deb=mid;
}
else {
fin=mid-1;
}
}
return get<2>(bonSurCol[col][deb]);
}
ll premSur(ll col,ll lig) {
ll deb=0,mid,fin=bonSurCol[col].size()-1;
while (deb!=fin) {
mid=(deb+fin)/2;
if (get<0>(bonSurCol[col][mid])>=lig) {
fin=mid;
}
else {
deb=mid+1;
}
}
return get<2>(bonSurCol[col][deb]);
}
ll dyna(ll idReq,ll desc) {
if (memo[idReq][desc]!=-1) {
return memo[idReq][desc];
}
ll col=posBon[idReq][0],num=posBon[idReq][1];
//cout<<idReq<<" : "<<premSous(col+1,get<0>(bonSurCol[col][num]))<<" "<<premSur(col+1,get<0>(bonSurCol[col][num]))<<endl;
//return 42;
if (desc==0) {
if (num==0) {
memo[idReq][desc]=dyna(idReq+2,1);
return memo[idReq][desc];
}
if (num==(ll)bonSurCol[col].size()-1) {
memo[idReq][desc]=max(get<1>(bonSurCol[col][num])+dyna(get<2>(bonSurCol[col][num-1]),0),
dyna(idReq+2,0));
}
else {
memo[idReq][desc]=max(get<1>(bonSurCol[col][num])+dyna(get<2>(bonSurCol[col][num-1]),0),
dyna(premSous(col+1,max(get<0>(bonSurCol[col][num+1])-1,(ll)0)),0));
}
return memo[idReq][desc];
}
else {
if (num==(ll)bonSurCol[col].size()-1) {
if (desc==1) {
memo[idReq][desc]=max(dyna(premSur(col+1,get<0>(bonSurCol[col][num-1])+1),1),dyna(idReq+2,0));
}
else {
memo[idReq][desc]=max(dyna(premSur(col+1,get<0>(bonSurCol[col][num-1])+1),1),dyna(idReq+2,1));
}
return memo[idReq][desc];
}
if (num==0) {
memo[idReq][desc]=max(dyna(idReq+3,0),
max(get<1>(bonSurCol[col][num])+dyna(get<2>(bonSurCol[col][num+1]),2),
dyna(idReq+2,1)));
return memo[idReq][desc];
}
memo[idReq][desc]=max(get<1>(bonSurCol[col][num])+dyna(get<2>(bonSurCol[col][num+1]),2),
dyna(premSur(col+1,get<0>(bonSurCol[col][num-1])+1),1));
return memo[idReq][desc];
}
}
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
taille=N;
nbBonus=M+2*(N+1);
for (ll i=0;i<M;i++) {
bonSurCol[X[i]].push_back(make_tuple(Y[i],W[i],i));
}
for (ll i=0;i<=taille;i++) {
bonSurCol[i].push_back(make_tuple(0,0,M+2*i));
bonSurCol[i].push_back(make_tuple(taille+1,0,M+2*i+1));
sort(bonSurCol[i].begin(),bonSurCol[i].end());
//cout<<i<<" : ";
for (ll j=0;j<(ll)bonSurCol[i].size();j++) {
//cout<<get<0>(bonSurCol[i][j])<<" "<<get<1>(bonSurCol[i][j])<<" "<<get<2>(bonSurCol[i][j])<<" ";
posBon[get<2>(bonSurCol[i][j])][0]=i;
posBon[get<2>(bonSurCol[i][j])][1]=j;
}
//cout<<endl;
}
for (ll i=0;i<nbBonus-2;i++) {
memo[i][0]=-1;
memo[i][1]=-1;
memo[i][2]=-1;
}
for (auto k:bonSurCol[taille-1]) {
memo[get<2>(k)][2]=-INFINI;
}
ll temp=dyna(M,1);
/*for (ll i=0;i<nbBonus;i++) {
for (ll j=0;j<3;j++) {
cout<<i<<" "<<j<<" : "<<dyna(i,j)<<endl;
}
}*/
return temp;
}
