#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long dp[400001][2];
struct catfish
{
int x,y,w;
catfish() {}
catfish(int _x,int _y,int _w)
{
x=_x;
y=_y;
w=_w;
}
bool operator<(const catfish&c)const
{
if(x==c.x)return y<c.y;
return x<c.x;
}
};
catfish a[400001];
int l[100001],r[100001];
long long maxx0[100001],maxx1[100001];
vector<long long> same[100001],nxt[100001],prv[100001],m1[100001],m2[100001],m3[100001];
vector<int> id1[100001],id2[100001];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W)
{
n=N;
m=M;
for(int i=0; i<n; i++)
{
X.push_back(i);
Y.push_back(n);
W.push_back(0);
l[i]=-1;
r[i]=-2;
}
for(int i=0; i<X.size(); i++)
a[i]= {X[i],Y[i],W[i]};
sort(a,a+X.size());
for(int i=0; i<X.size(); i++)
{
if(i==0||a[i].x!=a[i-1].x)l[a[i].x]=i;
if(i==X.size()-1||a[i].x!=a[i+1].x)r[a[i].x]=i;
}
long long ans=0;
for(int i=0;i<n;i++)
{
same[i].push_back({0});
for(int j=l[i]+1;j<=r[i];j++)
same[i].push_back(same[i][same[i].size()-1]+a[j-1].w);
if(i!=n-1)
{
int k=l[i+1]-1;
long long curr=0;
for(int j=l[i];j<=r[i];j++)
{
while(k<r[i+1]&&a[k+1].y<a[j].y)
{
k++;
curr+=a[k].w;
}
nxt[i].push_back(curr);
}
}
if(i!=0)
{
int k=l[i-1]-1;
long long curr=0;
for(int j=l[i];j<=r[i];j++)
{
while(k<r[i-1]&&a[k+1].y<a[j].y)
{
k++;
curr+=a[k].w;
}
id1[i].push_back(k-l[i-1]);
prv[i].push_back(curr);
}
}
if(i-2>=0)
{
int k=l[i-2]-1;
for(int j=l[i];j<=r[i];j++)
{
while(k<r[i-2]&&a[k+1].y<a[j].y)
{
k++;
}
id2[i].push_back(k-l[i-2]);
}
}
}
for(int i=0; i<X.size(); i++)
{
int x=a[i].x;
if(x-1>=0)
{
long long prec1=prv[x][i-l[x]];
long long prec2=same[x][i-l[x]];
for(int j=l[x-1]; j<=r[x-1]; j++)
{
if(a[j].y<a[i].y)dp[i][0]=max(dp[i][0],dp[j][0]+prec1-same[x-1][j-l[x-1]]);
if(a[j].y>=a[i].y)dp[i][1]=max(dp[i][1],max(dp[j][0],dp[j][1])+nxt[x-1][j-l[x-1]]-prec2);
}
}
if(x-2>=0)
{
long long prec3=prv[x][i-l[x]];
int h=id2[x][i-l[x]];
//cout<<h<<" "<<m3[x-2].size()<<" "<<m2[x-2].size()<<endl;
if(h>=0)dp[i][0]=m3[x-2][h]+prec3;
dp[i][0]=max(dp[i][0],m2[x-2][h+1]);
}
ans=max(ans,max(dp[i][0],dp[i][1]));
//cout<<a[i].x<<"---- "<<a[i].y<<" "<<a[i].w<<endl;
//cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
if(x!=n-1)ans=max(ans,max(dp[i][0],dp[i][1])+nxt[x][i-l[x]]);
if(i==r[x])
{
for(int j=l[x];j<=r[x];j++)
{
m1[x].push_back(dp[j][0]-same[x][j-l[x]]);
if(j!=l[x])m1[x][j-l[x]]=max(m1[x][j-l[x]],m1[x][j-l[x]-1]);
m3[x].push_back(max(dp[j][0],dp[j][1]));
if(j!=l[x])m3[x][j-l[x]]=max(m3[x][j-l[x]],m3[x][j-l[x]-1]);
m2[x].push_back(0);
}
if(x!=n-1)
for(int j=r[x];j>=l[x];j--)
{
m2[x][j-l[x]]=max(dp[j][0],dp[j][1])+nxt[x][j-l[x]];
if(j!=r[x])m2[x][j-l[x]]=max(m2[x][j-l[x]],m2[x][j-l[x]+1]);
}
}
}
return ans;
}
