#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned ll;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
#define N_ 101000
vc<pii>Z[N_];
vc<int>YY[N_], GG[N_];
vc<ll>D1[N_], D2[N_];
int n, m;
map<int,int>MM[N_];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
n=N,m=M;
rep(i,M){
Y[i]++;
Z[X[i]].pb({Y[i],W[i]});
MM[X[i]][Y[i]] = W[i];
}
rep(i,N){
sort(all(Z[i]));
}
rep(i,N){
rng(j,i-1,i+1){
if(j<0||j>=N)continue;
for(auto [y,w] : Z[j]){
YY[i].pb(y);
}
}
YY[i].pb(0);
sort(all(YY[i]));
YY[i].resize(unique(all(YY[i])) - YY[i].begin());
D1[i].resize(si(YY[i]));
D2[i].resize(si(YY[i]));
rep(j,si(YY[i])){
GG[i].pb(MM[i][YY[i][j]]);
}
}
ll INF = 1e18;
rng(i,1,N-1){
ll s = 0;
int pv = 0;
ll Mx = -INF;
ll pM = 0;
rep(j,si(YY[i-1])){
pM=max(pM, D1[i-1][j]);
pM=max(pM, D2[i-1][j]);
}
rep(j,si(YY[i])){
while(pv < si(YY[i-1]) && YY[i-1][pv] <= YY[i][j]){
int y = YY[i-1][pv];
int g = GG[i-1][pv];
s += g;
Mx=max(Mx, D1[i-1][pv]-s);
pv++;
}
D1[i][j] = max({D1[i][j], Mx + s, pM});
}
Mx = -INF;
pv = si(YY[i-1]) - 1;
per(j,si(YY[i])){
while(pv >= 0 && YY[i-1][pv] > YY[i][j]){
int y = YY[i-1][pv];
int g = MM[i][y];
Mx=max(Mx, max(D1[i-1][pv], D2[i-1][pv])-s);
pv--;
s += g;
}
D2[i][j] = max({D2[i][j], Mx + s, pM});
}
//printf("%d\n",i);
//rep(j,si(YY[i])){
//printf("%lld %lld\n",D1[i][j],D2[i][j]);
//}
}
ll ans=0;
rep(i,si(YY[N-1])){
ans=max({ans, D1[N-1][i], D2[N-1][i]});
}
return ans;
}
