#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back
void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}
template<typename T,typename V>
void PRINT(pair<T,V>& x){
cerr<<"{";
PRINT(x.fi);
cerr<<",";
PRINT(x.se);
cerr<<"}";
}
template<typename T>
void PRINT(T &x){
int id=0;
cerr<<"{";
for(auto _i:x){
cerr<<(id++ ? "," : "");
PRINT(_i);
}
cerr<<"}";
}
void _PRINT(){
cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
PRINT(h);
if(sizeof...(t)) cerr<<", ";
_PRINT(t...);
}
#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)
const int mxM=3e5+1;
const int mxN=1e5+1;
const int mxC=6e6;
int N,M;
ll seg0[mxC],left0[mxC],right0[mxC],roots0[mxN];
ll idx0;
void Update0(int node,int l,int r,int idx,ll val){
if(l==r){
seg0[node]+=val;
return;
}
if(idx<=mid){
if(!left0[node]) left0[node]=++idx0;
Update0(left0[node],l,mid,idx,val);
}
else{
if(!right0[node]) right0[node]=++idx0;
Update0(right0[node],mid+1,r,idx,val);
}
ll lnode=0; if(left0[node]) lnode=seg0[left0[node]];
ll rnode=0; if(right0[node]) rnode=seg0[right0[node]];
seg0[node]=lnode+rnode;
}
ll Query0(int node,int l,int r,int L,int R){
if(L>R) return 0;
if(L<=l && r<=R) return seg0[node];
ll ret=0;
if(L<=mid && left0[node]) ret+=Query0(left0[node],l,mid,L,R);
if(R>mid && right0[node]) ret+=Query0(right0[node],mid+1,r,L,R);
return ret;
}
struct Node{
ll i,d;
};
Node Merge1(Node n1,Node n2){
Node ret;
ret.i=max(n1.i,n2.i);
ret.d=max(n1.d,n2.d);
return ret;
}
Node seg1[mxC];
ll left1[mxC],right1[mxC];
ll idx1;
void Update1(int col,int node,int l,int r,int pier,Node val){
if(l==r){
seg1[node].i=val.i;
seg1[node].d=val.d;
seg1[node].i+=Query0(roots0[col],0,N-1,pier,N-1);
seg1[node].d+=Query0(roots0[col+1],0,N-1,0,pier-1);
return;
}
if(pier<=mid){
if(!left1[node]) left1[node]=++idx1;
Update1(col,left1[node],l,mid,pier,val);
}
else{
if(!right1[node]) right1[node]=++idx1;
Update1(col,right1[node],mid+1,r,pier,val);
}
Node lnode=Node(); if(left1[node]) lnode=seg1[left1[node]];
Node rnode=Node(); if(right1[node]) rnode=seg1[right1[node]];
seg1[node]=Merge1(lnode,rnode);
}
Node Query1(int node,int l,int r,int L,int R){
if(L>R) return Node();
if(L<=l && r<=R) return seg1[node];
Node ret=Node();
if(L<=mid && left1[node]) ret=Merge1(ret,Query1(left1[node],l,mid,L,R));
if(R>mid && right1[node]) ret=Merge1(ret,Query1(right1[node],mid+1,r,L,R));
return ret;
}
vector<int> piers[mxN];
vector<pair<int,ll>> w[mxN];
long long max_weights(int N1,int M1,vector<int> X,vector<int> Y,vector<int> W){
N=N1; M=M1; idx1=1;
for(int i=0;i<M;i++){
if(X[i]-1>=0) piers[X[i]-1].pb(Y[i]+1);
if(X[i]+1<N) piers[X[i]+1].pb(Y[i]+1);
w[X[i]].pb({Y[i],W[i]});
}
for(int i=0;i<N;i++){
if(!count(all(piers[i]),0)) piers[i].pb(0);
}
for(int i=0;i<N;i++){
roots0[i]=++idx0;
for(auto p:w[i]){
Update0(roots0[i],0,N-1,p.fi,p.se);
}
}
ll res=0;
int prev_root=-1,tmp_root=-1;
for(int i=0;i<N;i++){
if(i==0){
for(int p:piers[i]){
Update1(0,1,0,N,p,{0,0});
}
prev_root=1;
}
else{
tmp_root=++idx1;
for(int p:piers[i]){
Node tmp=Node();
Node n1=Query1(prev_root,0,N,0,p);
tmp.i=max(n1.i,n1.d)-Query0(roots0[i-1],0,N-1,p,N-1);
Node n2=Query1(prev_root,0,N,p+1,N);
tmp.d=max(n2.i,n2.d)-Query0(roots0[i],0,N-1,0,p-1);
if(i!=N-1) Update1(i,tmp_root,0,N,p,tmp);
res=max({res,tmp.i,tmp.d});
}
prev_root=tmp_root;
}
}
return res;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
