#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct node{
int s,e,m;
int val=0,lazy=0;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void propo(){
if (lazy==0) return;
val+=lazy;
if (s!=e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
void update(int i,int j,int k){
if (s==i && e==j) lazy+=k;
else{
if (j<=m) l->update(i,j,k);
else if (m<i) r->update(i,j,k);
else l->update(i,m,k),r->update(m+1,j,k);
l->propo(),r->propo();
val=max(l->val,r->val);
}
}
} *root;
int n,m;
vector<ii> arr[100005];
vector<int> pos[100005];
vector<int> w[100005];
vector<int> memo[2][2];
int max_weights(signed N, signed M, vector<signed> X, vector<signed> Y,
vector<signed> W) {
n=N,m=M;
rep(x,0,m) arr[X[x]+1].pub({Y[x],W[x]});
rep(x,0,n+2){
if (x==0 || x==n+1) arr[x].pub({0,0});
else arr[x].pub({n+1,0});
sort(all(arr[x]));
for (auto [a,b]:arr[x]){
pos[x].pub(a);
w[x].pub(b);
}
}
int a=0,b=1;
memo[a][0]=memo[a][1]={0};
rep(idx,1,n+2){
int ss1=sz(pos[idx-1]),ss2=sz(pos[idx]);
memo[b][0]=vector<int>(ss2,0); //contribution counted
memo[b][1]=vector<int>(ss2,0); //contribution not counted
rep(i,0,2) rep(j,0,2){
root=new node(0,ss1-1);
rep(x,0,ss1) root->update(x,x,memo[a][i][x]);
rep(y,0,sz(pos[idx])) if (j==0){
int z=ub(all(pos[idx-1]),pos[idx][y])-pos[idx-1].begin();
if (z<ss1) root->update(z,ss1-1,w[idx][y]);
}
int z=0;
rep(y,0,sz(pos[idx])){
if (i==1){
while (z<sz(pos[idx-1]) && pos[idx-1][z]<pos[idx][y]){
root->update(0,z,w[idx-1][z]);
z++;
}
}
root->propo();
memo[b][j][y]=max(memo[b][j][y],root->val);
if (j==0){
int z=ub(all(pos[idx-1]),pos[idx][y])-pos[idx-1].begin();
if (z<ss1) root->update(z,ss1-1,-w[idx][y]);
}
}
}
swap(a,b);
//cout<<"idx: "<<idx<<endl;
//for (auto it:memo[a][0]) cout<<it<<" "; cout<<endl;
//for (auto it:memo[a][1]) cout<<it<<" "; cout<<endl;
}
return memo[a][0][0];
}
