#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));
for (ll i = 2; i <= n; i++)
{
states.clear();
for (auto j : fish[i])
if (j.first != -1)
states.push_back(j.first);
for (auto j : fish[i - 1])
if (j.first != -1)
states.push_back(j.first);
states.push_back(0);
states.push_back(n);
sort(states.begin(), states.end());
for (ll x : states)
{
dp[i][1].push_back(make_pair(x, -inf));
for (auto j : dp[i - 1][1])
if (j.first <= x)
{
ll l = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(j.first, inf)) - 1 - fish[i - 1].begin();
ll r = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(x, inf)) - 1 - fish[i - 1].begin();
dp[i][1].back().second = max(dp[i][1].back().second, j.second + fish[i - 1][r].second - fish[i - 1][l].second);
}
for (auto j : from0[i - 1])
{
ll pos = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(x, inf)) - fish[i - 1].begin() - 1;
dp[i][1].back().second = max(dp[i][1].back().second, j.first + max(0ll, fish[i - 1][pos].second - j.second));
}
dp[i][0].push_back(dp[i][1].back());
for (auto j : dp[i - 1][0])
if (j.first >= x)
{
ll l = upper_bound(fish[i].begin(), fish[i].end(), make_pair(x, inf)) - fish[i].begin() - 1;
ll r = upper_bound(fish[i].begin(), fish[i].end(), make_pair(j.first, inf)) - fish[i].begin() - 1;
dp[i][0].back().second = max(dp[i][0].back().second, j.second + fish[i][r].second - fish[i][l].second);
}
}
for (auto j : dp[i - 1][0])
{
ll pos = upper_bound(fish[i].begin(), fish[i].end(), make_pair(j.first, inf)) - fish[i].begin() - 1;
from0[i].push_back(make_pair(j.second + fish[i][pos].second, fish[i][pos].second));
}
}
ll ans = 0;
for (auto i : dp[n][0]) ans = max(ans, i.second);
for (auto i : dp[n][1]) ans = max(ans, i.second);
if (n == 1) assert(ans == 0);
return ans;
}
