#include"fish.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const long long INF=1e18;
vector< pair<int,int> > vi[MAXN];
set<int> st,sp;
long long dp[MAXN][2],pre[MAXN][2],fen[MAXN],dn[MAXN],p1[MAXN],p2[MAXN];
void update(int i,int n,long long val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
long long get(int i) { long long ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
struct segmenttree
{
long long seg[MAXN*4];
void update(int l,int r,int i,long long val,int pos)
{
if(i<l||r<i) return ;
if(l==r)
{
seg[pos]=val;
return ;
}
int mid=(l+r)/2;
update(l,mid,i,val,pos*2);
update(mid+1,r,i,val,pos*2+1);
seg[pos]=max(seg[pos*2],seg[pos*2+1]);
}
long long get(int l,int r,int u,int v,int pos)
{
if(v<l||r<u) return -INF;
if(u<=l&&r<=v) return seg[pos];
int mid=(l+r)/2;
return max(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1));
}
};
segmenttree sa,sb;
void maximize(long long& a,long long b)
{
if(a<b) a=b;
}
long long max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W)
{
for(int i=0;i<M;i++) vi[X[i]+1].push_back({Y[i]+1,W[i]});
for(int i=0;i<=N;i++) dp[i][0]=dp[i][1]=pre[i][0]=pre[i][1]=-INF;
dp[0][0]=0,st={0,N},dn[0]=-INF;
for(int i=1;i<=(N+1)*4;i++) sa.seg[i]=sb.seg[i]=-INF;
for(int i=1;i<=N+1;i++)
{
sp=st,st.clear(),st={0,N};
for(auto v:vi[i-1]) st.insert(v.first);
for(auto v:vi[i]) st.insert(v.first);
for(auto v:vi[i-1]) update(v.first,N,v.second);
for(auto v:sp) p1[v]=get(v);
for(auto v:st) p1[v]=get(v);
for(auto v:vi[i-1]) update(v.first,N,-v.second);
for(auto v:vi[i]) update(v.first,N,v.second);
for(auto v:sp) p2[v]=get(v);
for(auto v:st) p2[v]=get(v);
for(auto v:sp)
{
pre[v][0]=dp[v][0],pre[v][1]=dp[v][1],dp[v][0]=dp[v][1]=-INF;
sa.update(0,N,v,pre[v][0]-p1[v],1);
sb.update(0,N,v,max(pre[v][0],pre[v][1])+p2[v],1);
}
for(auto v:vi[i]) update(v.first,N,-v.second);
maximize(dp[0][0],pre[0][1]);
for(auto v:st)
{
dp[v][0]=p1[v]-sa.get(0,N,0,v,1);
dp[v][1]=sb.get(0,N,v,N,1)-p2[v];
}
if(i>1) maximize(dp[N][0],dn[i-2]+p1[N]);
dn[i]=max(dp[N][0],dp[N][1]);
for(auto v:sp)
{
sa.update(0,N,v,-INF,1);
sb.update(0,N,v,-INF,1);
}
}
return max(dp[0][0],dp[0][1]);
}
