#include<bits/stdc++.h>
#include "fish.h"
#define pb push_back
#define SZ(x) ((int)((x).size()))
const int N=100005;typedef std::pair<int,int> pi;
template <typename _Tp>inline void chmax(_Tp &a,const _Tp &b){a=a<b?b:a;}
std::vector<pi> vec[N];std::vector<int> f[N][2];int pre1[N],pre2[N];
long long max_weights(int n,int m,std::vector<int> X,std::vector<int> Y,std::vector<int> W){
	for(int i=0;i<m;++i)vec[X[i]].pb({Y[i],W[i]});
	for(int i=0;i<n;++i){
		vec[i].pb({n,0}),std::sort(vec[i].begin(),vec[i].end());
		if(vec[i][0].first!=0)vec[i].insert(vec[i].begin(),(pi){0,0});
	}
	for(int i=0;i<n;++i)f[i][0].resize(SZ(vec[i])),f[i][1].resize(SZ(vec[i]));
	for(int i=0;i<SZ(vec[0]);++i)f[0][0][i]=0,f[0][1][i]=0;
	for(int i=1;i<n;++i){
		int mx=0;for(int j=0;j<SZ(vec[i-1]);++j)chmax(mx,f[i-1][1][j]);
		for(int j=0;j<SZ(vec[i]);++j)chmax(f[i][0][j],mx),chmax(f[i][1][j],mx);
		for(int j=1;j<SZ(vec[i]);++j)pre2[j]=pre2[j-1]+vec[i][j-1].second;
		for(int j=1,p=0,s=0;j<SZ(vec[i-1]);++j){
			while(p<SZ(vec[i])&&vec[i][p].first<vec[i-1][j].first)s+=vec[i][p++].second;
			pre1[j]=s;
		}
		mx=0;for(int j=0;j<SZ(vec[i-1]);++j)chmax(mx,f[i-1][1][j]+pre1[j]);
		for(int j=1;j<SZ(vec[i]);++j)chmax(f[i][1][j],mx-pre2[j]);
		for(int j=1;j<SZ(vec[i-1]);++j)pre1[j]=pre1[j-1]+vec[i-1][j-1].second;
		for(int j=1,p=0,s=0;j<SZ(vec[i]);++j){
			while(p<SZ(vec[i-1])&&vec[i-1][p].first<vec[i][j].first)s+=vec[i-1][p++].second;
			pre2[j]=s;
		}
		mx=0;for(int j=0;j<SZ(vec[i-1]);++j)chmax(mx,f[i-1][0][j]-pre1[j]);
		for(int j=0;j<SZ(vec[i]);++j)chmax(f[i][0][j],mx+pre2[j]);
	}
	int ans=0;for(int i=0;i<SZ(vec[n-1]);++i)ans=std::max({ans,f[n-1][0][i],f[n-1][1][i]});
	return ans;
}