#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (ll i = s; i <= e; ++i)
#define rrep(i,s,e) for (ll i = s; i >= e; --i)
#define len(v) (ll)v.size()
#define pb push_back
#define all(v) v.begin(), v.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef pair<ll,ll> pll;
ll max_weights(int n, int m, vi X, vi Y, vi W) {
bool done[n+5] = {};
vector<ll> check[n+5], fish[n+5];
unordered_map<ll,ll> w[n+5], dp[n+5][2];
rep (i,0,m-1) {
fish[X[i]+1].pb(Y[i]+1);
w[X[i]+1][Y[i]+1] = W[i];
check[X[i]+1].pb(Y[i]);
if (Y[i]==0) done[X[i]+1] = 1;
}
rep (i,0,n) {
if (i) check[i].pb(n);
if (!done[i]) check[i].pb(0);
}
rep (i,1,n) {
ll sth = 0;
{
//go bigger
vector<pll> upd;
set<ll> st;
for (ll el : check[i]) upd.pb({el,1});
for (ll el : fish[i-1]) upd.pb({el,0});
for (ll el : check[i-1]) upd.pb({el,2});
sort (all(upd));
ll sum = 0;
for (pll el : upd) {
ll y = el.fi, tp = el.se;
if (tp==0) {
sum += w[i-1][y];
}
if (tp==1) {
ll res;
if (len(st)) {
res = sum+*st.rbegin();
}
else res = 0;
dp[i][0][y] = max(dp[i][0][y], res);
if (y==n) sth = res;
//cout << "1: " << i << " " << y << " " << dp[i][0][y] << endl;
}
if (tp==2) {
st.insert(dp[i-1][0][y]-sum);
}
}
}
{
//go smaller
vector<pll> upd;
ll sum = 0, cur = 0;
for (ll el : check[i]) upd.pb({el,3});
for (ll el : fish[i+1]) {
upd.pb({el, 0});
sum += w[i+1][el];
}
for (ll el : fish[i]) {
upd.pb({el, 1});
cur += w[i][el];
}
for (ll el : check[i-1]) upd.pb ({el, 2});
sort (all(upd));
reverse(all(upd));
set<ll> st;
for (pll el : upd) {
ll y = el.fi, tp = el.se;
if (tp==0) sum -= w[i+1][y];
if (tp==1) cur -= w[i][y];
if (tp==2) st.insert({dp[i-1][1][y]});
if (tp==3) {
ll res = dp[i-1][0][n]+cur;
if (len(st)) res = max(res, *st.rbegin());
if (y==n) res = max(res, sth+cur);
dp[i][1][y] = res-cur+sum;
////cout << "2: " << i << " " << y << " " << dp[i][1][y] << endl;
dp[i+1][0][y] = dp[i][1][y];
}
}
}
}
ll ans = 0;
for (ll y : check[n]) {
ans = max(ans, dp[n][0][y]);
ans = max(ans, dp[n][1][y]);
}
return ans;
}
