#include"fish.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
vector<pair<int,int>>fish[100001];
vector<ll>sum_down[100001];
vector<ll>sum_right[100001];
vector<ll>sum_left[100001];
int h[100001];
vector<ll>dp1[1000001];
vector<bool>dpt1[1000001];
vector<ll>dp2[1000001];
vector<bool>dpt2[1000001];
vector<ll>dp3[1000001];
vector<bool>dpt3[1000001];
ll dp4[1000001];
bool dpt4[1000001];
ll get_slope_down(int x,int y);
ll get_slope_up(int x,int y);
ll get_gap(int x,ll min_sum);
ll get_full(int x);
ll get_slope_down(int x,int y){
if(x==n-1){
return 0;
}
if(dpt1[x][y])
return dp1[x][y];
ll res=0;
for(int y2=0;y2<h[x+1];y2++){
if(fish[x][y].first>=fish[x][y2].first){
ll res2=get_slope_down(x+1,y2)-sum_down[x][y]+sum_right[x][y];
res=max(res,res2);
}
}
ll res2=get_gap(x+1,sum_right[x][y])-sum_down[x][y];
res=max(res,res2);
dpt1[x][y]=true;
dp1[x][y]=res;
return res;
}
ll get_slope_up(int x,int y){
if(x==n-1){
return 0;
}
if(dpt2[x][y])
return dp2[x][y];
ll res=0;
for(int y2=0;y2<h[x+1];y2++){
if(fish[x][y].first<=fish[x][y2].first){
ll res2=get_slope_up(x+1,y2)-sum_down[x][y]+sum_left[x][y];
res=max(res,res2);
}
}
ll res2=get_full(x+1)+sum_left[x+1].back()-sum_down[x][y]+sum_left[x][y];
res=max(res,res2);
dpt2[x][y]=true;
dp2[x][y]=res;
return res;
}
ll get_gap(int x,ll min_sum){
if(x==n-1)
return min_sum;
ll res=0;
res=max(res,get_full(x+1)+sum_left[x+1].back());
for(int y2=0;y2<h[x+1];y2++){
ll res2=get_slope_up(x+1,y2)+max(sum_left[x+1][y2],min_sum);
res=max(res,res2);
}
return res;
}
ll get_full(int x){
if(x==n-1)
return 0;
if(dpt4[x])
return dp4[x];
ll res=0;
res=max(res,get_gap(x+1,sum_right[x].back()));
for(int y2=0;y2<h[x+1];y2++){
ll res2=get_slope_down(x+1,y2)+sum_right[x].back();
res=max(res,res2);
}
dpt4[x]=true;
dp4[x]=res;
return res;
}
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
n=N+1;
for(int i=0;i<M;i++)
fish[X[i]+1].push_back({Y[i],W[i]});
for(int i=0;i<n;i++)
sort(fish[i].begin(),fish[i].end());
for(int i=0;i<n;i++)
fish[i].push_back({n,0});
for(int i=0;i<n;i++)
h[i]=(int)fish[i].size();
for(int i=0;i<n;i++){
sum_down[i].resize(h[i]);
for(int j=1;j<h[i];j++){
sum_down[i][j]=sum_down[i][j-1]+fish[i][j-1].second;
}
}
for(int i=0;i<n;i++){
dp1[i].resize(h[i]);
dpt1[i].resize(h[i]);
dp2[i].resize(h[i]);
dpt2[i].resize(h[i]);
dp3[i].resize(h[i]);
dpt3[i].resize(h[i]);
}
sum_right[n-1].resize(h[n-1]);
for(int i=0;i<n-1;i++){
sum_right[i].resize(h[i]);
int i2=0;
ll sum=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i+1]&&fish[i][i1].first>fish[i+1][i2].first){
sum+=fish[i+1][i2].second;
i2++;
}
sum_right[i][i1]=sum;
}
}
sum_left[0].resize(h[0]);
for(int i=1;i<n;i++){
sum_left[i].resize(h[i]);
int i2=0;
ll sum=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i-1]&&fish[i][i1].first>fish[i-1][i2].first){
sum+=fish[i-1][i2].second;
i2++;
}
sum_left[i][i1]=sum;
}
}
return get_gap(0,0);
}
