#include "fish.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=1LL<<60;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<vector<pair<int,ll>>> fish(N);
rep(i,M) {
fish[X[i]].emplace_back(Y[i],W[i]);
}
rep(i,N) {
fish[i].emplace_back(N,0);
}
vector<vector<int>> pos(N);
vector<vector<ll>> cum_lf(N);
vector<vector<ll>> cum_ri(N);
vector<vector<ll>> cum_hr(N);
vector<vector<ll>> updp(N);
vector<vector<ll>> dndp(N);
vector<int> sz(N);
rep(i,N) {
sort(all(fish[i]));
sz[i]=fish[i].size();
updp[i].resize(sz[i],-INF);
dndp[i].resize(sz[i],-INF);
if(i!=0) {
ll cum=0;
int cnt=0;
for(auto &[y,_]:fish[i]){
while(fish[i-1][cnt].first<y){
cum+=fish[i-1][cnt].second;
cnt++;
}
cum_lf[i].emplace_back(cum);
}
}
if(i!=N-1){
ll cum=0;
int cnt=0;
for(auto &[y,_]:fish[i]){
while(fish[i+1][cnt].first<y){
cum+=fish[i+1][cnt].second;
cnt++;
}
cum_ri[i].emplace_back(cum);
}
}
cum_hr[i].emplace_back(0);
for(auto &[_,w]:fish[i]) {
cum_hr[i].emplace_back(cum_hr[i].back()+w);
}
}
rep(i,fish[0].size()) {
updp[0][i]=0;
dndp[0][i]=0;
}
rng(i,1,N) {
int cnt=0;
ll mx=-INF;
rep(j,sz[i]) {
while(cnt<sz[i-1]&&fish[i-1][cnt].first<=fish[i][j].first) {
mx=max(mx,updp[i-1][cnt]-cum_hr[i-1][cnt]);
cnt++;
}
updp[i][j]=mx+cum_lf[i][j];
}
cnt=sz[i-1]-1;
mx=-INF;
rrep(j,sz[i]) {
while(cnt>=0&&fish[i-1][cnt].first>=fish[i][j].first) {
mx=max(mx,dndp[i-1][cnt]+cum_ri[i-1][cnt]);
cnt--;
}
dndp[i][j]=mx-cum_hr[i][j];
}
if(i>=2) {
cnt=0;
mx=-INF;
rep(j,sz[i]) {
while(cnt<sz[i-2]&&fish[i-2][cnt].first<=fish[i][j].first) {
mx=max(mx,dndp[i-2][cnt]);
cnt++;
}
updp[i][j]=max(updp[i][j],mx+cum_lf[i][j]);
}
cnt=sz[i-2]-1;
mx=-INF;
rrep(j,sz[i]) {
while(0<=cnt&&fish[i-2][cnt].first>=fish[i][j].first) {
mx=max(mx,dndp[i-2][cnt]+cum_ri[i-2][cnt]);
cnt--;
}
updp[i][j]=max(updp[i][j],mx);
}
}
rep(j,sz[i]) {
dndp[i][j]=max(dndp[i][j],updp[i][j]);
}
}
ll ans=-INF;
for(ll i:dndp.back())ans=max(ans,i);
return ans;
}
