#include"fish.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
typedef long long ll;
int n;
vector<pair<int,int>>fish[100001];
vector<ll>sum_down[100001];
vector<ll>sum_right_pos[100001];
vector<ll>sum_left_pos[100001];
vector<ll>next_right[100001];
vector<ll>next_left[100001];
int h[100001];
ll full_sum[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,int min_y);
ll get_full(int x);
ll get_sum_right(int x,int y){
return sum_down[x+1][sum_right_pos[x][y]];
}
ll get_sum_left(int x,int y){
return sum_down[x-1][sum_left_pos[x][y]];
}
/*ll get1(int y2,int x){
if(y2<0)
return LLONG_MIN;
ll res=get_slope_down(x+1,y2);
res=max(res,get1(y2-1,x));
return res;
}*/
ll get_slope_down(int x,int y){
if(x==n-1){
return 0;
}
if(dpt1[x][y])
return dp1[x][y];
ll res=LLONG_MIN;
for(int y2=0;y2<next_right[x][y];y2++){
ll res2=get_slope_down(x+1,y2)-sum_down[x][y]+get_sum_right(x,y);
res=max(res,res2);
}
ll res2=get_gap(x+1,sum_right_pos[x][y])-sum_down[x][y];
res=max(res,res2);
dpt1[x][y]=true;
dp1[x][y]=res;
return res;
}
/*ll get2(int y2,int x){
if(y2<0)
return LLONG_MIN;
ll res=get_slope_up(x+1,y2);
res=max(res,get2(y2-1,x));
return res;
}*/
ll get_slope_up(int x,int y){
if(x==n-1){
return get_sum_left(x,y);
}
if(dpt2[x][y])
return dp2[x][y];
ll res=LLONG_MIN;
for(int y2=0;y2<h[x+1];y2++){
if(fish[x][y].first<=fish[x+1][y2].first){
ll res2=get_slope_up(x+1,y2)-sum_down[x][y]+get_sum_left(x,y);
res=max(res,res2);
}
}
ll res2=get_full(x+1)+full_sum[x]-sum_down[x][y]+get_sum_left(x,y);
res=max(res,res2);
dpt2[x][y]=true;
dp2[x][y]=res;
return res;
}
ll get_gap(int x,int min_y){
if(x==n-1)
return sum_down[x][min_y];
if(dpt3[x][min_y])
return dp3[x][min_y];
ll res=get_full(x+1)+full_sum[x];
res=max(res,get_gap(x+1,0)+sum_down[x][min_y]);
for(int y2=0;y2<h[x+1];y2++){
ll res2=get_slope_up(x+1,y2)+max(get_sum_left(x+1,y2),sum_down[x][min_y])-get_sum_left(x+1,y2);
res=max(res,res2);
}
dpt3[x][min_y]=true;
dp3[x][min_y]=res;
return res;
}
ll get_full(int x){
if(x==n-1)
return 0;
if(dpt4[x])
return dp4[x];
ll res=get_gap(x+1,h[x+1]-1);
res=max(res,get_full(x+1));
for(int y2=0;y2<h[x+1];y2++){
ll res2=get_slope_down(x+1,y2)+full_sum[x+1];
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]});
full_sum[X[i]+1]+=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+1,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_pos[n-1].resize(h[n-1]);
for(int i=0;i<n-1;i++){
sum_right_pos[i].resize(h[i]);
next_right[i].resize(h[i]);
int i2=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i+1]-1&&fish[i][i1].first>fish[i+1][i2].first){
i2++;
}
sum_right_pos[i][i1]=i2;
}
i2=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i+1]&&fish[i][i1].first>=fish[i+1][i2].first)
i2++;
next_right[i][i1]=i2;
}
}
sum_left_pos[0].resize(h[0]);
for(int i=1;i<n;i++){
sum_left_pos[i].resize(h[i]);
next_left[i].resize(h[i]);
int i2=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i-1]-1&&fish[i][i1].first>fish[i-1][i2].first){
i2++;
}
sum_left_pos[i][i1]=i2;
}
i2=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i-1]&&fish[i][i1].first>=fish[i-1][i2].first)
i2++;
next_left[i][i1]=i2;
}
}
return get_gap(0,0);
}
