#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
const ll inf = 2e18;
long long max_weights(int n, int m, vector<int> X, vector<int> Y,
vector<int> W)
{
vector<pair<ll, ll>> fish[n + 1];
for (ll i = 0; i < m; i++)
fish[X[i] + 1].push_back(make_pair(Y[i] + 1, W[i]));
for (ll i = 1; i <= n; i++)
{
sort(fish[i].begin(), fish[i].end());
fish[i].insert(fish[i].begin(), make_pair(-1, 0));
for (ll j = 1; j < fish[i].size(); j++)
fish[i][j].second += fish[i][j - 1].second;
}
vector<pair<ll, ll>> dp[n + 1][2];
vector<pair<ll, ll>> from0[n + 1];
vector<ll> states;
for (auto j : fish[1])
if (j.first != -1)
dp[1][1].push_back(make_pair(j.first, 0)), dp[1][0].push_back(make_pair(j.first, 0));
dp[1][1].push_back(make_pair(n, 0));
dp[1][0].push_back(make_pair(n, 0));
from0[1].push_back(make_pair(0, 0));
vector<pair<ll, ll>> pre, suf;
for (ll i = 2; i <= n; i++)
{
states.clear();
for (auto j : fish[i])
if (j.first != -1)
states.push_back(j.first), states.push_back(j.first - 1);
for (auto j : fish[i - 1])
if (j.first != -1)
states.push_back(j.first), states.push_back(j.first - 1);
states.push_back(n);
sort(states.begin(), states.end());
states.resize(unique(states.begin(), states.end()) - states.begin());
pre.clear();
pre.push_back(make_pair(-1, -inf));
for (auto j : dp[i - 1][1])
{
ll l = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(j.first, inf)) - 1 - fish[i - 1].begin();
pre.push_back(make_pair(j.first, max(pre.back().second, j.second - fish[i - 1][l].second)));
}
suf.clear();
suf.push_back(make_pair(n + 1, -inf));
for (ll j = (ll)dp[i - 1][0].size() - 1; j >= 0; j--)
{
ll r = upper_bound(fish[i].begin(), fish[i].end(), make_pair(dp[i - 1][0][j].first, inf)) - fish[i].begin() - 1;
suf.push_back(make_pair(dp[i - 1][0][j].first, max(suf.back().second, dp[i - 1][0][j].second + fish[i][r].second)));
}
reverse(suf.begin(), suf.end());
ll mx = -inf, mx1 = -inf;
for (auto j : from0[i - 1])
mx = max(mx, j.second - j.first), mx1 = max(mx1, j.second);
for (ll x : states)
{
dp[i][1].push_back(make_pair(x, -inf));
ll r = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(x, inf)) - 1 - fish[i - 1].begin(), pos = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(x, inf)) - fish[i - 1].begin() - 1, l = upper_bound(fish[i].begin(), fish[i].end(), make_pair(x, inf)) - fish[i].begin() - 1;
dp[i][1].back().second = max({dp[i][1].back().second, (--upper_bound(pre.begin(), pre.end(), make_pair(x, inf)))->second + fish[i - 1][r].second, fish[i - 1][pos].second + mx, mx1});
dp[i][0].push_back(dp[i][1].back());
dp[i][0].back().second = max(dp[i][0].back().second, (lower_bound(suf.begin(), suf.end(), make_pair(x, inf)))->second - fish[i][l].second);
}
assert(dp[i][1].size() == dp[i][0].size());
for (ll j = 0; j < dp[i - 1][0].size(); j++)
{
ll pos = upper_bound(fish[i].begin(), fish[i].end(), make_pair(dp[i - 1][0][j].first, inf)) - fish[i].begin() - 1;
from0[i].push_back(make_pair(fish[i][pos].second, max(dp[i - 1][0][j].second, dp[i - 1][1][j].second) + fish[i][pos].second));
}
}
ll ans = 0;
for (auto i : dp[n][0]) ans = max(ans, i.second);
return ans;
}
