//#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define imx INT_MAX
const long long MMX = (long long)(1e18);
typedef long long LL;
vector<pair<int,LL> > dw[100005],val[100005];
vector<pair<int,pair<int,int> > >up[100005];
vector<pair<LL,int> >lup[100005],ldw[100005],lze[100005];
vector<LL>rup[100005];
int c1,c2,si1,si2,c3,cr,crr;
LL ze[100005],rr,rrdw,rrup;
long long max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
for(int i=0;i<M;i++){
up[X[i]+2].pb({Y[i]+1,{W[i],-1}});
up[X[i]].pb({Y[i]+1,{W[i],1}});
dw[X[i]].pb({Y[i]+1,W[i]});
val[X[i]+1].pb({Y[i]+1,W[i]});
}
for(int i=1;i<=N;i++){
sort(all(up[i]));
sort(all(dw[i]));
sort(all(val[i]));
}
lze[0].pb({0,0});
for(int i=1;i<=N;i++){
for(int j=0;j<dw[i].size();j++){
ldw[i].pb({0,dw[i][j].F});
if(j!=0)dw[i][j].S+=dw[i][j-1].S;
}
c1=lup[i-1].size()-1,c2=ldw[i-1].size()-1,c3=val[i].size()-1,rr=-1;
rrdw=0;
for(int j=0;j<val[i].size();j++)rrdw+=val[i][j].S;
for(int j=ldw[i].size()-1;j>-1;j--){
cr=ldw[i][j].S;
if(c1!=-1){
while(lup[i-1][c1].S>=cr){
rr=max(rr,lup[i-1][c1].F);
c1--;
if(c1==-1)break;
}
}
if(c2!=-1){
while(ldw[i-1][c2].S>=cr){
rr=max(rr,ldw[i-1][c2].F);
c2--;
if(c2==-1)break;
}
}
if(c3!=-1){
while(val[i][c3].F>cr){
rrdw-=val[i][c3].S;
c3--;
if(c3==-1)break;
}
}
if(rr==-1)continue;
ldw[i][j].F=rr+dw[i][j].S-rrdw;
}
c1=0,c2=0,c3=0,rrup=0,rrdw=0,rr=-MMX;
for(int j=0;j<up[i].size();j++){
rrup+=up[i][j].S.F;
if(j!=up[i].size()-1){
if(up[i][j].F==up[i][j+1].F)continue;
}
cr=up[i][j].F;
if(c1!=lup[i-1].size()){
while(lup[i-1][c1].S<=cr){
crr=lup[i-1][c1].S;
if(c2!=val[i-1].size()){
while(val[i-1][c2].F<=crr){
rrdw-=val[i-1][c2].S;
c2++;
if(c2==val[i-1].size())break;
}
}
if(c3!=val[i].size()){
while(val[i][c3].F<=crr){
rrdw-=val[i][c3].S;
c3++;
if(c3==val[i].size())break;
}
}
//printf("// %lld",rrdw);
rr=max(rr,lup[i-1][c1].F+rrdw);
c1++;
if(c1==lup[i-1].size())break;
}
}
rup[i].pb(rrup);
if(rr==-MMX){
lup[i].pb({0,up[i][j].F});
continue;
}
//printf("=/ %lld %lld",rrup,rr);
lup[i].pb({rrup+rr,up[i][j].F});
}
c1=lze[i-1].size()-1,c2=val[i-1].size()-1,rrdw=0,rr=-1;
for(int j=0;j<val[i-1].size();j++)rrdw-=val[i-1][j].S;
for(int j=lup[i].size()-1;j>-1;j--){
cr=lup[i][j].S;
if(c1!=-1){
while(lze[i-1][c1].S>=cr){
rr=max(rr,lze[i-1][c1].F);
c1--;
if(c1==-1)break;
}
}
if(c2!=-1){
while(val[i-1][c2].F>cr){
rrdw+=val[i-1][c2].S;
c2--;
if(c2==-1)break;
}
}
if(rr==-1)continue;
//printf("//%d %lld\n",lup[i][j].S,rr+rup[i][j]+rrdw);
lup[i][j].F=max(lup[i][j].F,rr+rup[i][j]+rrdw);
}
c1=0,c2=0,rr=-1,rrdw=0;
for(int j=0;j<lup[i].size();j++){
cr=lup[i][j].S;
if(c1!=lze[i-1].size()){
while(lze[i-1][c1].S<=cr){
crr=lze[i-1][c1].S;
if(c2!=val[i-1].size()){
while(val[i-1][c2].F<=crr){
rrdw-=val[i-1][c2].S;
c2++;
if(c2==val[i-1].size())break;
}
}
rr=max(rr,lze[i-1][c1].F+rrdw);
c1++;
if(c1==lze[i-1].size())break;
}
}
if(rr==-1)continue;
lup[i][j].F=max(lup[i][j].F,rr+rup[i][j]);
}
lze[i].pb({ze[i-1],0});
si1=lup[i-1].size();
si2=ldw[i-1].size();
lup[i-1].pb({0,imx});
ldw[i-1].pb({0,imx});
for(c1=0,c2=0;c1<si1||c2<si2;){
ze[i]=max(ze[i],lup[i-1][c1].F);
ze[i]=max(ze[i],ldw[i-1][c2].F);
if(lup[i-1][c1].S<ldw[i-1][c2].S){
lze[i].pb(lup[i-1][c1]);
c1++;
}
else if(lup[i-1][c1].S>ldw[i-1][c2].S){
lze[i].pb(ldw[i-1][c2]);
c2++;
}
else{
lze[i].pb({max(lup[i-1][c1].F,ldw[i-1][c2].F),lup[i-1][c1].S});
c1++,c2++;
}
}
//printf("=%d=\n",i);
// for(int j=0;j<lup[i].size();j++)printf("%lld %d\n",lup[i][j].F,lup[i][j].S);
// for(int j=0;j<ldw[i].size();j++)printf("[%lld %d]\n",ldw[i][j].F,ldw[i][j].S);
// for(int j=0;j<lze[i].size();j++)printf("{%lld %d}\n",lze[i][j].F,lze[i][j].S);
}
LL ans=0;
for(int i=0;i<lze[N].size();i++)ans=max(ans,lze[N][i].F);
for(int i=0;i<lup[N].size();i++)ans=max(ans,lup[N][i].F);
for(int i=0;i<ldw[N].size();i++)ans=max(ans,ldw[N][i].F);
return ans;
}
