#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int max_weights(signed n, signed m, vector<signed> x, vector<signed> y, vector<signed> w){
vector<vector<pii> > vect(n);
vector<vector<vector<int> > > dp(n), down(n);
vector<vector<int> > l(n), up(n);
for (int i=0; i<m; ++i)vect[x[i]].pb(mp(y[i]+1, w[i]));
for (int i=0; i<n; ++i){
vect[i].pb(mp(0, 0));
sort(vect[i].begin(), vect[i].end());
for (int j=1; j<vect[i].size(); ++j)vect[i][j].se+=vect[i][j-1].se;
}
for (int i=0; i<n; ++i){
l[i].pb(0);
if (i)for (auto a:vect[i-1])l[i].pb(a.fi);
if (i!=n-1)for (auto a:vect[i+1])l[i].pb(a.fi);
sort(l[i].begin(), l[i].end());
l[i].erase(unique(l[i].begin(), l[i].end()), l[i].end());
dp[i].resize(l[i].size(), vector<int>(2, 0));
down[i].resize(l[i].size(), vector<int>(2, 0));
up[i].resize(l[i].size(), 0);
}
int i=0;
for (int j=l[i].size()-1; j>=0; --j)up[i][j]=max((j!=l[i].size()-1?up[i][j+1]:0), max(dp[i][j][0], dp[i][j][1])+(upper_bound(vect[i+1].begin(), vect[i+1].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
for (int j=0; j<l[i].size(); ++j)down[i][j][0]=max((j?down[i][j-1][0]:0), dp[i][j][0]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
for (int j=0; j<l[i].size(); ++j)down[i][j][1]=max((j?down[i][j-1][1]:0), dp[i][j][1]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
for (int i=1; i<n; ++i){
for (int j=0; j<l[i].size(); ++j){
int id=upper_bound(l[i-1].begin(), l[i-1].end(), l[i][j])-l[i-1].begin()-1;
dp[i][j][0]=max(down[i-1][id][0]+(upper_bound(vect[i-1].begin(), vect[i-1].end(), mp(l[i][j], LLONG_MAX/2))-1)->se, down[i-1][id][1]);
dp[i][j][1]=up[i-1][id]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se;
}
if (i==n-1)continue;
for (int j=l[i].size()-1; j>=0; --j)up[i][j]=max((j!=l[i].size()-1?up[i][j+1]:0), max(dp[i][j][0], dp[i][j][1])+(upper_bound(vect[i+1].begin(), vect[i+1].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
for (int j=0; j<l[i].size(); ++j)down[i][j][0]=max((j?down[i][j-1][0]:0), dp[i][j][0]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
for (int j=0; j<l[i].size(); ++j)down[i][j][1]=max((j?down[i][j-1][1]:0), dp[i][j][1]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
}
int ans=0;
for (auto a:dp[n-1])ans=max({ans, a[0], a[1]});
return ans;
}
