#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int MAX=3e5+5;
const ll INF=1LL<<60;
vector<pii> V[MAX]; // {y,w}
vector<int> hs[MAX];
vector<ll> dp0,dp1; // up,down
vector<ll> nxt0,nxt1;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){
for (int i=0;i<M;i++){
Y[i]++;
V[X[i]].push_back({Y[i],W[i]});
if (X[i]>0) hs[X[i]-1].push_back(Y[i]);
if (X[i]<N-1) hs[X[i]+1].push_back(Y[i]);
}
for (int i=0;i<N;i++){
sort(V[i].begin(),V[i].end());
V[i].resize(unique(V[i].begin(),V[i].end())-V[i].begin());
hs[i].push_back(0);
sort(hs[i].begin(),hs[i].end());
hs[i].resize(unique(hs[i].begin(),hs[i].end())-hs[i].begin());
}
ll ans=0;
dp0.push_back(0),dp1.push_back(0);
for (int i=0;i<N;i++){
nxt0.clear(),nxt1.clear();
vector<ll> adj0,adj1; // adjusted
int hs0=i==0?1:hs[i-1].size();
int hs1=hs[i].size();
int fs0=i==0?0:V[i-1].size();
int fs1=V[i].size();
nxt0.resize(hs1),adj0.resize(hs0);
nxt1.resize(hs1),adj1.resize(hs0);
// Up
ll p=0;
int fi=0;
for (int hi=0;hi<hs0;hi++){
int h=i==0?0:hs[i-1][hi];
while (fi<fs0&&V[i-1][fi].first<=h) p-=V[i-1][fi].second,fi++;
adj0[hi]=dp0[hi]+p;
}
p=-INF;
ll q=0;
int hj=0;
fi=0;
for (int hi=0;hi<hs1;hi++){
int h=hs[i][hi];
while (hj<hs0&&(i==0||hs[i-1][hj]<=h)) p=max(p,adj0[hj]),hj++;
while (fi<fs0&&V[i-1][fi].first<=h) q+=V[i-1][fi].second,fi++;
nxt0[hi]=q+p;
}
// Down
p=0;
fi=0;
for (int hi=0;hi<hs0;hi++){
int h=i==0?0:hs[i-1][hi];
while (fi<fs1&&V[i][fi].first<=h) p+=V[i][fi].second,fi++;
adj1[hi]=dp1[hi]+p;
}
p=-INF;
q=0; for (int fi=0;fi<fs1;fi++) q-=V[i][fi].second;
hj=hs0-1;
fi=fs1-1;
for (int hi=hs1-1;hi>=0;hi--){
int h=hs[i][hi];
while (hj>=0&&(i==0?0:hs[i-1][hj])>=h) p=max(p,adj1[hj]),hj--;
while (fi>=0&&V[i][fi].first>h) q+=V[i][fi].second,fi--;
nxt1[hi]=q+p;
}
// Stuff
/*
cout<<i<<'\n';
for (auto h:hs[i]) cout<<h<<' ';
cout<<'\n';
cout<<'\n';
for (auto a:nxt0) cout<<a<<' ';
cout<<'\n';
for (auto a:nxt1) cout<<a<<' ';
cout<<'\n';
cout<<'\n';
/**/
for (int hi=0;hi<hs1;hi++){
if (i>0) nxt0[hi]=max(nxt0[hi],dp1[0]);
nxt1[hi]=max(nxt1[hi],nxt0[hi]);
}
for (int hi=0;hi<hs1;hi++) ans=max(ans,max(nxt0[hi],nxt1[hi]));
swap(nxt0,dp0),swap(nxt1,dp1);
}
return ans;
}
