#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long inf=1e18;
long long mxa[100069][2];
vector<pair<long long,long long>> vl[100069];
struct segtree
{
long long l,r,mx;
segtree *p[2];
void bd(long long lh,long long rh)
{
l=lh;
r=rh;
mx=-inf;
if(l<r)
{
long long ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
}
}
void ud(long long x,long long w)
{
if(l>x||r<x);
else if(l>=x&&r<=x)
{
mx=max(mx,w);
}
else
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->ud(x,w);
}
mx=max(p[0]->mx,p[1]->mx);
}
}
long long qr(long long lh,long long rh)
{
if(l>rh||r<lh)
{
return -inf;
}
else if(l>=lh&&r<=rh)
{
return mx;
}
else
{
return max(p[0]->qr(lh,rh),p[1]->qr(lh,rh));
}
}
}
sg[2];
long long max_weights(int n,int m,vector<int> xa,vector<int> ya,vector<int> wg)
{
long long i,j,ii,x,y,w,l,l2,sz,z=-inf;
for(i=1;i<=m;i++)
{
x=xa[i-1]+1;
y=ya[i-1]+1;
w=wg[i-1];
vl[x].push_back({y,w});
}
for(ii=0;ii<2;ii++)
{
sg[ii].bd(1,n);
}
for(i=1;i<=n;i++)
{
sort(vl[i].begin(),vl[i].end());
l=mxa[i-1][1];
l2=-inf;
if(i-2>=0)
{
l2=max(mxa[i-2][0],mxa[i-2][1]);
}
sz=vl[i].size();
for(j=0;j<sz;j++)
{
y=vl[i][j].fr;
w=vl[i][j].sc;
sg[0].ud(y,max(sg[0].qr(1,y-1),max(l,l2))+w);
}
for(j=sz-1;j>=0;j--)
{
y=vl[i][j].fr;
w=vl[i][j].sc;
sg[1].ud(y,max(sg[1].qr(y+1,n),l2)+w);
}
for(ii=0;ii<2;ii++)
{
mxa[i][ii]=max(mxa[i-1][ii],sg[ii].mx);
}
}
z=max(mxa[n][1],mxa[n-1][0]);
return z;
}
