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