#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,int> > v[100001];
int dp[300001][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[300001];
int l[100001],r[100001];
int p[300001];
int sum(int x,int dw,int up)
{
if(l[x]==-1)return 0;
if(up<a[l[x]].y)return 0;
if(a[r[x]].y<dw)return 0;
int id1=-1,id2=-1;
int lf=l[x],rt=r[x];
while(lf<=rt)
{
int md=(lf+rt)/2;
if(a[md].y>=dw)
{
id1=md;
rt=md-1;
}
else lf=md+1;
}
lf=l[x],rt=r[x];
while(lf<=rt)
{
int md=(lf+rt)/2;
if(a[md].y<=up)
{
id2=md;
lf=md+1;
}
else rt=md-1;
}
if(id1>id2)return 0;
int ans=p[id2]-p[id1]+a[id1].w;
/*for(int i=l[x];i<=r[x];i++)
cout<<i<<" - "<<a[i].x<<" "<<a[i].y<<" "<<a[i].w<<endl;
cout<<x<<" !! "<<dw<<" "<<up<<" "<<id1<<" "<<id2<<" "<<p[id1]<<" "<<p[id2]<<endl;*/
return ans;
}
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]=W[i];
if(i)p[i]+=p[i-1];
}
int ans=0;
for(int i=0;i<X.size();i++)
{
//cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].w<<endl;
int x=a[i].x;
if(x-1>=0)
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]+sum(x-1,a[j].y,a[i].y-1));
if(a[j].y>=a[i].y)dp[i][1]=max(dp[i][1],max(dp[j][0],dp[j][1])+sum(x,a[i].y,a[j].y-1));
}
if(x-2>=0)
for(int j=l[x-2];j<=r[x-2];j++)
{
dp[i][0]=max(dp[i][0],max(dp[j][0],dp[j][1])+sum(x-1,0,max(a[j].y,a[i].y)-1));
}
ans=max(ans,max(dp[i][0],dp[i][1]));
if(x!=n-1)ans=max(ans,max(dp[i][0],dp[i][1])+sum(x+1,0,a[i].y-1));
}
return ans;
}
