#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const ll maxn = 6e5 + 10 , inf = 1e18+ 10 , mod = 998244353;
vector <int> vec[maxn] ;
vector <ll> mx2[maxn] , pmx[maxn] , smx[maxn] , smx2[maxn] ;
vector <pair<int,ll > > sf[maxn] ;
ll dp[maxn][2] ;
int n ;
long long max_weights(int N, int m, std::vector<int> X, std::vector<int> Y,std::vector<int> W){
n = N ;
rep(i , 0, m-1){
vec[X[i]].pb(Y[i]);
sf[X[i]].pb({Y[i] , W[i]});
}
rep(i , 0 ,n-1){
vec[i].pb(n) ;
sf[i].pb({n ,0}) ;
}
rep(i , 0 ,n-1){
sort(all(vec[i])) ;
sort(all(sf[i])) ;
per(j , sz(sf[i])-2 , 0){
sf[i][j].S += sf[i][j+1].S;
}
}
int sm = 0 ;
rep(i , 0 ,n-1){
if(i!=0)
rep(j , 0 ,sz(vec[i])-1){
int id = sm + j;
int xx = lower_bound(all(vec[i-1]) , vec[i][j]) - vec[i-1].begin() ;
int xx2 = lower_bound(all(vec[i-1]) , vec[i][j]+1) - vec[i-1].begin();
ll mx ;
if(xx2)mx = max(pmx[i-1][xx2-1] , -sf[i-1][xx].S + mx2[i-1][xx2-1]);
else mx = -inf ;
if(xx2 < sz(smx[i-1])){
dp[id][0] = max(dp[id][0] , smx[i-1][xx2]);
dp[id][1] = max(dp[id][1] , smx2[i-1][xx2] + sf[i][j].S) ;
}
rep(k2 , 0 ,sz(vec[i-1])-1){
int k = sm - sz(vec[i-1]) + k2 ;
if(vec[i-1][k2] <= vec[i][j]){
// mx = max({mx , dp[k][1] , dp[k][0] + sf[i-1][k2].S - sf[i-1][xx].S} );
}else{
// dp[id][0] = max(dp[id][0] , dp[k][1]) ;
int zz =lower_bound(all(vec[i]) , vec[i-1][k2]) - vec[i].begin() ;
// dp[id][1] = max(dp[id][1] , dp[k][1] + sf[i][j].S - sf[i][zz].S);
}
}
dp[id][0] = max(dp[id][0] , mx);
dp[id][1] = max(dp[id][1] , mx) ;
// cout << i << " " << vec[i][j] << " : " << dp[id][0] << " " << dp[id][1] << "\n";
}
rep(j , 0 ,sz(vec[i])-1){
mx2[i].pb(dp[sm+j][0] + sf[i][j].S) ;
pmx[i].pb(dp[sm+j][1]);
if(j!=0){
mx2[i].back() = max(mx2[i].back() , mx2[i][sz(mx2[i])-2]) ;
pmx[i].back() = max(pmx[i].back() , pmx[i][sz(pmx[i])-2]) ;
}
}
if(i==n-1)break ;
rep(j , 0 , sz(vec[i])-1){
smx[i].pb(dp[sm+j][1]);
int zz =lower_bound(all(vec[i+1]) , vec[i][j]) - vec[i+1].begin() ;
smx2[i].pb(dp[sm+j][1] - sf[i+1][zz].S) ;
}
per(j , sz(vec[i])-2 , 0){
smx[i][j] = max(smx[i][j] , smx[i][j+1]) ;
smx2[i][j] = max(smx2[i][j] , smx2[i][j+1]);
}
sm += sz(vec[i]) ;
}
ll ans =0 ;
rep(i , 0 , sm-1){
ans = max({ans , dp[i][0] , dp[i][1]}) ;
}
return ans;
}
