#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;
vector<int> inds[mxN];
map<int,ll> dp[3][mxN],val[mxN];
map<int,ll,greater<int>> pref[mxN];
void CalcPref(int x){
for(auto p:val[x]){
int y=p.fi;
ll w=p.se;
pref[x][y]=w+(!pref[x].empty() ? (*prev(pref[x].begin())).se : 0LL);
}
}
ll Sum(int x,int y1,int y2){
if(pref[x].empty() || y1>y2) return 0;
else{
int r=(*(pref[x].lower_bound(y2))).se;
int l=(*(pref[x].lower_bound(y1-1))).se;
return r-l;
}
}
ll MaxThree(int x,int p){
return max({dp[0][x][p],dp[1][x][p],dp[2][x][p]});
}
long long max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W){
for(int i=0;i<M;i++){
val[X[i]][Y[i]]=W[i];
if(X[i]-1>=0) inds[X[i]-1].pb(Y[i]+1);
if(X[i]+1<N) inds[X[i]+1].pb(Y[i]+1);
}
for(int x=0;x<N;x++){
inds[x].pb(0); inds[x].pb(N);
sort(all(inds[x]));
inds[x].resize(distance(inds[x].begin(),unique(all(inds[x]))));
}
for(int x=0;x<N;x++){
CalcPref(x);
if(x==0){
for(int p:inds[x]){
dp[0][x][p]=dp[1][x][p]=dp[2][x][p]=0;
}
}
else{
int i1=sz(inds[x-1])-1,i2=sz(inds[x])-1;
ll mx=0;
while(i2>=0){
int p1=inds[x-1][i1],p2=inds[x][i2];
while(i1>=0 && p1>p2){
ll tmp=max(dp[1][x-1][p1],dp[2][x-1][p1])+Sum(x,p2,p1-1);
mx=max(mx,tmp);
i1--;
}
dp[2][x][p2]=mx;
if(i2>0 && mx!=0){
int np2=inds[x][i2-1];
mx+=Sum(x,np2,p2-1);
}
i2--;
}
//Debug(1);
mx=0;
i1=0,i2=0;
while(i2<sz(inds[x])){
int p1=inds[x-1][i1],p2=inds[x][i2];
while(i1<sz(inds[x-1]) && p1<p2){
ll tmp=max(dp[1][x-1][p1],dp[0][x-1][p1])+Sum(x,p1,p2-1);
mx=max(mx,tmp);
i1++;
}
dp[0][x][p2]=mx;
if(i2<sz(inds[x])-1 && mx!=0){
int np2=inds[x][i2+1];
mx+=Sum(x,p2,np2-1);
}
i2++;
}
//Debug(2);
for(int p:inds[x]){
dp[1][x][p]=MaxThree(x-1,p);
}
if(x>1){
i1=sz(inds[x-2])-1,i2=sz(inds[x])-1;
mx=0;
while(i2>=0){
int p1=inds[x-2][i1],p2=inds[x][i2];
while(i1>=0 && p1>=p2){
ll tmp=MaxThree(x-2,p1)+Sum(x-1,0,p1-1);
mx=max(mx,tmp);
i1--;
}
dp[0][x][p2]=max(dp[0][x][p2],mx);
i2--;
}
i1=0,i2=0;
mx=0;
while(i2<sz(inds[x])){
int p1=inds[x-2][i1],p2=inds[x][i2];
while(i1<sz(inds[x-2]) && p1<p2){
ll tmp=MaxThree(x-2,p1)+Sum(x-1,0,p2-1);
mx=max(mx,tmp);
i1++;
}
dp[0][x][p2]=max(dp[0][x][p2],mx);
i2++;
}
for(int p:inds[x]){
dp[2][x][p]=max(dp[2][x][p],MaxThree(x-1,N))+Sum(x,p,N-1);
}
}
}
}
ll res=0;
for(int p:inds[N-1]){
res=max(res,MaxThree(N-1,p));
}
return res;
}
