#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 seg[mxC],_l[mxC],_r[mxC],roots[mxC];
int idxx;
void Update(int node,int l,int r,int idx,ll val){
if(l==r){
seg[node]+=val;
return;
}
if(idx<=mid){
if(!_l[node]) _l[node]=++idxx;
Update(_l[node],l,mid,idx,val);
}
else{
if(!_r[node]) _r[node]=++idxx;
Update(_r[node],mid+1,r,idx,val);
}
seg[node]=(_l[node] ? seg[_l[node]] : 0)+(_r[node] ? seg[_r[node]] : 0);
}
ll Query(int node,int l,int r,int L,int R){
if(L>R) return 0;
if(L<=l && r<=R) return seg[node];
ll ret=0;
if(L<=mid && _l[node]) ret+=Query(_l[node],l,mid,L,R);
if(R>mid && _r[node]) ret+=Query(_r[node],mid+1,r,L,R);
return ret;
}
ll Query(int col,int L,int R){
return Query(roots[col],0,N-1,L,R);
}
vector<int> piers[mxN];
vector<pair<int,ll>> w[mxN];
vector<ll> dp[2][mxN];
vector<ll> mx(mxN);
void MaxSelf(ll& x,ll v){
x=max(x,v);
}
long long max_weights(int N1,int M1,vector<int> X,vector<int> Y,vector<int> W){
N=N1; M=M1;
ll sum0=0,sum1=0;
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]});
if(X[i]==0) sum0+=W[i];
else sum1+=W[i];
}
for(int i=0;i<N;i++){
sort(all(piers[i]));
piers[i].resize(distance(piers[i].begin(),unique(all(piers[i]))));
sort(all(w[i]));
roots[i]=++idxx;
for(auto p:w[i]){
Update(roots[i],0,N-1,p.fi,p.se);
}
dp[0][i].resize(sz(piers[i]));
dp[1][i].resize(sz(piers[i]));
}
for(int i=0;i<N;i++){
if(i){
if(i>=3){
for(int j=0;j<sz(piers[i]);j++){
int p=piers[i][j];
MaxSelf(dp[0][i][j],mx[i-3]+Query(i-1,0,p-1));
}
}
if(i>=2){
int j1=-1;
ll pref=0;
for(int j=0;j<sz(piers[i]);j++){
int p=piers[i][j];
while(j1+1<sz(piers[i-2]) && piers[i-2][j1+1]<=p){
MaxSelf(pref,max(dp[0][i-2][j1+1],dp[1][i-2][j1+1]));
j1++;
}
MaxSelf(dp[0][i][j],pref+Query(i-1,0,p-1));
}
j1=sz(piers[i-2]);
pref=0;
for(int j=sz(piers[i])-1;j>=0;j--){
int p=piers[i][j];
while(j1-1>=0 && piers[i-2][j1-1]>p){
MaxSelf(pref,max(dp[0][i-2][j1-1],dp[1][i-2][j1-1])+Query(i-1,0,piers[i-2][j1-1]-1));
j1--;
}
MaxSelf(dp[0][i][j],pref);
}
}
for(int j=0;j<sz(piers[i]);j++){
int p=piers[i][j];
MaxSelf(dp[0][i][j],Query(i-1,0,p-1));
}
int j1=-1;
ll pref=0;
for(int j=0;j<sz(piers[i]);j++){
int p=piers[i][j];
while(j1+1<sz(piers[i-1]) && piers[i-1][j1+1]<=p){
MaxSelf(pref,dp[0][i-1][j1+1]+Query(i-1,piers[i-1][j1+1],N-1));
j1++;
}
MaxSelf(dp[0][i][j],pref-Query(i-1,p,N-1));
}
j1=sz(piers[i-1]);
pref=0;
for(int j=sz(piers[i])-1;j>=0;j--){
int p=piers[i][j];
while(j1-1>=0 && piers[i-1][j1-1]>p){
MaxSelf(pref,max(dp[0][i-1][j1-1],dp[1][i-1][j1-1])+Query(i,0,piers[i-1][j1-1]-1));
j1--;
}
MaxSelf(dp[1][i][j],pref-Query(i,0,p-1));
}
}
if(i+1<N){
for(int j=0;j<sz(piers[i]);j++){
int p=piers[i][j];
MaxSelf(mx[i],max(dp[0][i][j],dp[1][i][j])+Query(i+1,0,p-1));
}
if(i) MaxSelf(mx[i],mx[i-1]);
}
}
ll res=mx[N-2];
for(int j=0;j<sz(piers[N-1]);j++){
res=max(res,max(dp[0][N-1][j],dp[1][N-1][j]));
}
return res;
}
