#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,int> > v[400001];
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[400001],r[400001];
long long p[400001];
vector<long long> same[400001],nxt[400001],prv[400001];
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;
p[i]=a[i].w;
if(i)p[i]+=p[i-1];
}
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;
}
prv[i].push_back(curr);
}
}
}
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]];
for(int j=l[x-2]; j<=r[x-2]; j++)
{
long long help=0;
if(a[i].y>a[j].y)help=prec3;
else help=nxt[x-2][j-l[x-2]];
dp[i][0]=max(dp[i][0],max(dp[j][0],dp[j][1])+help);
}
}
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]]);
}
return ans;
}
