#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long max_weights(int N, int MM, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<pair<int, ll>>P[N];
vector<int>Q_[N + 4];
vector<int>*Q = Q_ + 2;
for (int i = 0; i < MM; i++)
{
P[X[i]].push_back({Y[i], W[i]});
Q[X[i]].push_back(Y[i]);
}
for (int i = -1; i <= N; i++)
{
Q[i].push_back(N);
}
for (int i = 0; i < N; i++)
{
sort(P[i].begin(), P[i].end());
for (int j = 1; j < (int)P[i].size(); j++)
P[i][j].second += P[i][j - 1].second;
sort(Q[i].begin(), Q[i].end());
}
ll dp_[N + 3];
ll* dp = dp_ + 2;
for (int i = -2; i <= N; i++)
dp[i] = 0;
vector<ll> u[N];
vector<ll> d[N];
auto get = [&](int x, int y)->ll
{
if (x < 0 || x >= N)
return 0;
auto it = lower_bound(P[x].begin(), P[x].end(), make_pair(y + 1, -1ll));
if (it == P[x].begin())
return 0;
it--;
return it->second;
};
ll vv = 0;
for (int x = 0; x < N; x++)
{
dp[x] = dp[x - 1];
dp[x] = max(dp[x], vv);
vv = 0;
for (int y : Q[x - 1])
u[x].push_back(0);
for (int y : Q[x + 1])
d[x].push_back(0);
for (int i = 0; i < (int)Q[x - 1].size(); i++)
{
ll&v = u[x][i];
int y = Q[x - 1][i];
v = max(v, dp[x - 1]);
v = max(v, dp[x - 2] + get(x - 1, y));
}
if (x != 0)
{
ll mx = -1e18;
int j = 0;
for (int i = 0; i < (int)Q[x - 1].size(); i++)
{
ll&v = u[x][i];
int y = Q[x - 1][i];
while (j < (int)Q[x - 2].size() && Q[x - 2][j] < y)
{
mx = max(mx, u[x - 1][j] - get(x - 1, Q[x - 2][j]));
j++;
}
v = max(v, mx + get(x - 1, y));
}
}
for (int i = 0; i < (int)Q[x - 1].size(); i++)
{
ll&v = u[x][i];
int y = Q[x - 1][i];
dp[x] = max(dp[x], v);
vv = max(vv, v + get(x + 1, y));
}
for (int i = 0; i < (int)Q[x + 1].size(); i++)
{
ll&v = d[x][i];
int y = Q[x + 1][i];
if (y == N)
v = max(v, u[x].back());
v = max(v, dp[x - 1]);
v = max(v, dp[x - 2] + get(x - 1, y));
}
if (x != 0)
{
int j = (int)Q[x].size() - 1;
ll mx = -1e18;
for (int i = (int)Q[x + 1].size() - 1; i >= 0; i--)
{
ll&v = d[x][i];
int y = Q[x + 1][i];
while (j >= 0 && Q[x][j] > y)
{
mx = max(mx, d[x - 1][j] + get(x, Q[x][j]));
j--;
}
v = max(v, mx - get(x, y));
}
}
for (int i = 0; i < (int)Q[x + 1].size(); i++)
{
ll&v = d[x][i];
int y = Q[x + 1][i];
dp[x] = max(dp[x], v);
vv = max(vv, v + get(x + 1, y));
}
}
return dp[N - 1];
}
