#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>slope_down_dp[1000001];
vector<ll>slope_down_dp_max[1000001];
vector<ll>slope_up_dp[1000001];
vector<ll>slope_up_dp_max[1000001];
vector<ll>dp_max1[1000001];
vector<ll>dp_max2[1000001];
vector<ll>gap_dp[1000001];
ll full_dp[1000001];
ll get_sum_right(int x,int y){
if(x==n-1)
return 0;
return sum_down[x+1][sum_right_pos[x][y]];
}
ll get_sum_left(int x,int y){
if(x==0)
return 0;
return sum_down[x-1][sum_left_pos[x][y]];
}
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++){
slope_down_dp[i].resize(h[i]);
slope_down_dp_max[i].resize(h[i]+1);
slope_up_dp[i].resize(h[i]);
slope_up_dp_max[i].resize(h[i]+1);
gap_dp[i].resize(h[i]);
dp_max1[i].resize(h[i]+1);
dp_max2[i].resize(h[i]+1);
}
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;
}
}
for(int y=0;y<h[n-1];y++){
slope_up_dp[n-1][y]=get_sum_left(n-1,y);
gap_dp[n-1][y]=sum_down[n-1][y];
}
for(int x=n-2;x>=0;x--){
slope_down_dp_max[x+1][0]=-1e17;
for(int y=1;y<=h[x+1];y++){
slope_down_dp_max[x+1][y]=max(slope_down_dp_max[x+1][y-1],slope_down_dp[x+1][y-1]);
}
slope_up_dp_max[x+1][h[x+1]]=-1e17;
for(int y=h[x+1]-1;y>=0;y--){
slope_up_dp_max[x+1][y]=max(slope_up_dp_max[x+1][y+1],slope_up_dp[x+1][y]);
}
dp_max1[x+1][0]=-1e17;
for(int y=1;y<=h[x+1];y++){
dp_max1[x+1][y]=max(dp_max1[x+1][y-1],slope_up_dp[x+1][y-1]-get_sum_left(x+1,y-1));
}
dp_max2[x+1][h[x+1]]=-1e17;
for(int y=h[x+1]-1;y>=0;y--){
dp_max2[x+1][y]=max(dp_max2[x+1][y+1],slope_up_dp[x+1][y]+get_sum_left(x+1,y)-get_sum_left(x+1,y));
}
for(int y=0;y<h[x];y++){
//slope down
{
ll res=slope_down_dp_max[x+1][next_right[x][y]];
res+=-sum_down[x][y]+get_sum_right(x,y);
ll res2=gap_dp[x+1][sum_right_pos[x][y]]-sum_down[x][y];
slope_down_dp[x][y]=max(res,res2);
}
// slope up
{
ll res=slope_up_dp_max[x+1][next_right[x][y]]-sum_down[x][y]+get_sum_left(x,y);
ll res2=full_dp[x+1]+full_sum[x]-sum_down[x][y]+get_sum_left(x,y);
slope_up_dp[x][y]=max(res,res2);
}
// gap
{
ll res=full_dp[x+1]+full_sum[x];
res=max(res,gap_dp[x+1][0]+sum_down[x][y]);
int l=-1,r=h[x+1];
while(l<r-1){
int m=(l+r)/2;
if(get_sum_left(x+1,m)>sum_down[x][y]){
r=m;
}else{
l=m;
}
}
int y_point=r;
res=max(res,dp_max1[x+1][y_point]+sum_down[x][y]);
/*for(int y2=0;y2<y_point;y2++){
ll res2=slope_up_dp[x+1][y2]-get_sum_left(x+1,y2);
res=max(res,res2);
}*/
res=max(res,dp_max2[x+1][y_point]);
/*for(int y2=y_point;y2<h[x+1];y2++){
ll res2=slope_up_dp[x+1][y2]+get_sum_left(x+1,y2)-get_sum_left(x+1,y2);
res=max(res,res2);
}*/
gap_dp[x][y]=res;
}
}
// full
{
ll res=gap_dp[x+1][h[x+1]-1];
res=max(res,full_dp[x+1]);
for(int y2=0;y2<h[x+1];y2++){
ll res2=slope_down_dp[x+1][y2]+full_sum[x+1];
res=max(res,res2);
}
full_dp[x]=res;
}
}
return gap_dp[0][0];
}
