#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3,unroll-loops")
const ll inf=-1e18;
struct seg{
int l,r;
seg *lf,*rg;
ll val=inf;
void build(int x,int y){
l=x,r=y;
if(l==r){
return;
}
int mid=(l+r)/2;
lf=new seg(), rg=new seg();
lf->build(l,mid),rg->build(mid+1,r);
}
void update(int pos,ll brp){
if(l==r){
val=max(val,brp); return;
}
int mid=(l+r)/2;
if(mid>=pos)lf->update(pos,brp);
else rg->update(pos,brp);
val=max(lf->val,rg->val);
}
ll query(int posl,int posr){
if(l>posr || r<posl)return inf;
if(l>=posl && r<=posr)return val;
int mid=(l+r)/2;
return max(lf->query(posl,posr),rg->query(posl,posr));
}
} slv[2];
vector<pair<int,int> >v[100002];
long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
slv[0].build(0,n-1); slv[1].build(0,n-1);
for(int q=0;q<m;q++){
v[X[q]].push_back({Y[q],W[q]});
}
vector<vector<ll> >dp(n+2,vector<ll>(2,inf));
dp[0][0]=dp[0][1]=0;
for(int q=0;q<n;q++){
sort(v[q].begin(),v[q].end());
// 0=inc 1=dec
for(auto [y,w] : v[q]){
ll brp=max(dp[q][1],slv[0].query(0,y-1)); // pakai dp[q][1] (dari prv all)
if(q){
brp=max({brp,dp[q-1][1]});
}
slv[0].update(y,brp+w);
}
for(int t=v[q].size()-1;t>=0;t--){
auto [y,w] =v[q][t];
ll brp=slv[1].query(y+1,n-1);
if(q){
brp=max({brp,dp[q-1][0],dp[q-1][1]});
}
slv[1].update(y,brp+w);
}
dp[q+1][0]=max(dp[q][0],slv[0].val); // coba penuh
dp[q+1][1]=max(dp[q][1],slv[1].val); // coba kosong
}
return max(dp[n][1],dp[n-1][0]);
}
