#include "fish.h"
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 300000
#define inf 1e9
using namespace std;
struct reads
{
    int y,d;
    bool operator < (const reads &t)const
    {
	return y<t.y;
    }
};
vector<reads>p[N+1];
vector<long long>dp[N+1][2];
long long F[N+1];
long long max_weights(int n,int m,vector<int>X,vector<int>Y,vector<int>w)
{
    long long ps,res,res2;
    for (int i=1;i<=n;++i) p[i].push_back((reads){n+1,0});
    for (int i=0;i<m;++i) p[X[i]+1].push_back((reads){Y[i]+1,w[i]});
    for (int i=1;i<=n;++i) sort(p[i].begin(),p[i].end()),dp[i][0].resize(p[i].size()),dp[i][1].resize(p[i].size());
    for (int i=2;i<=n;++i)
    {
	//00
	ps=-1,res=-inf;
	for (int j=0;j<p[i].size();++j)
	{
	    while (ps+1<p[i-1].size()&&p[i-1][ps+1].y<p[i][j].y) ++ps,res=max(res,dp[i-1][0][ps])+p[i-1][ps].d;
	    if (ps+1<p[i-1].size()&&p[i-1][ps+1].y==p[i][j].y)
	    {
		dp[i][0][j]=max(dp[i][0][j],max(dp[i-1][0][ps+1],dp[i-1][1][ps+1]));
		dp[i][1][j]=max(dp[i][1][j],max(dp[i-1][0][ps+1],dp[i-1][1][ps+1]));
	    }
	    dp[i][0][j]=max(dp[i][0][j],res);
	}
	//11
	ps=(int)(p[i-1].size()),res=-inf;
	for (int j=(int)(p[i].size())-1;j>=0;--j)
	{
	    while (ps-1>=0&&p[i-1][ps-1].y>p[i][j].y) --ps,res=max(res,dp[i-1][1][ps]);
	    res+=p[i][j].d;
	    dp[i][1][j]=max(dp[i][1][j],res);
	}
	//10
	if (i>=3)
	{
	    ps=(int)(p[i-2].size()),res=-inf;
	    for (int j=(int)(p[i-1].size())-1;j>=0;--j)
	    {
		while (ps-1>=0&&p[i-2][ps-1].y>p[i-1][j].y) --ps,res=max(res,dp[i-2][1][ps]);
		F[j]=res;
	    }
	    res2=0;
	    for (int j=0;j<p[i-1].size();++j) res2+=p[i-1][j].d,F[j]+=res2;
	    ps=-1;
	    for (int j=0;j<p[i].size();++j)
	    {
		while (ps+1<p[i-1].size()&&p[i-1][ps+1].y<p[i][j].y) ++ps,res=max(res,F[ps]);
		dp[i][0][j]=max(dp[i][0][j],res);
	    }
	}
	//01
	for (int j=0;j<p[i].size();++j) dp[i][1][j]=max(dp[i][1][j],dp[i][0][j]);
    }
    res=-inf;
    for (int i=0;i<p[n].size();++i) res=max(res,max(dp[n][0][i],dp[n][1][i]));
    return res;
}