#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void chmax(ll& x, ll y) {
x = max(x, y);
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<vector<array<ll, 2>>> a(N + 3);
for (int i = 0; i < M; ++i) {
a[X[i] + 1].push_back({Y[i] + 1, W[i]});
}
for (int i = 1; i < N; ++i) {
a[i].push_back({0, 0});
a[i].push_back({N + 1, 0});
for (auto& u : a[i + 1]) {
a[i].push_back({u[0], 0});
}
}
for (int i = N; i > 1; --i) {
a[i].push_back({0, 0});
a[i].push_back({N + 1, 0});
for (auto& u : a[i - 1]) {
a[i].push_back({u[0], 0});
}
}
for (int i = 1; i <= N; ++i) {
sort(begin(a[i]), end(a[i]));
vector<array<ll, 2>> unq{a[i][0]};
for (int j = 1; j < (int)a[i].size(); ++j) {
if (unq.back()[0] != a[i][j][0]) {
unq.push_back(a[i][j]);
} else {
unq.back()[1] = a[i][j][1];
}
}
a[i] = unq;
}
// for (int i = 1; i <= N; ++i) {
// for (auto& [x, w] : a[i]) {
// cout << x << " " << w << "\n";
// }
// cout << "\n";
// }
vector<vector<array<ll, 2>>> dp(N + 2);
for (int i = 1; i <= N; ++i) {
dp[i].resize(a[i].size() + 1);
}
// 1 - for hi <= h(i - 1)
// 0 - for hi >= h(i - 1)
for (int i = 2; i <= N; ++i) {
// cerr << i << "\n";
ll res = 0;
int ptr = a[i - 1].size() - 1;
for (int j = (int)a[i].size() - 1; j >= 0; --j) {
while (ptr >= 0 && a[i - 1][ptr][0] >= a[i][j][0]) {
res = max({res, dp[i - 1][ptr][0], dp[i - 1][ptr][1]});
ptr -= 1;
}
dp[i][j][1] = max(dp[i][j][1], res);
res += a[i][j][1];
}
res = 0;
ptr = 0;
for (int j = 0; j < (int)a[i].size(); ++j) {
while (ptr < (int)a[i - 1].size() && a[i - 1][ptr][0] <= a[i][j][0]) {
res = max(res, dp[i - 1][ptr][1]);
ptr += 1;
}
dp[i][j][0] = max(res, dp[i][j][0]);
}
res = 0;
ptr = 0;
for (int j = 0; j < (int)a[i].size(); ++j) {
while (ptr < (int)a[i - 1].size() && a[i - 1][ptr][0] <= a[i][j][0]) {
res = max(res + a[i - 1][ptr][1], dp[i - 1][ptr][0]);
ptr += 1;
}
dp[i][j][0] = max(dp[i][j][0], res);
}
}
// for (int i = 1; i <= N; ++i) {
// for (int j = 0; j < (int)a[i].size(); ++j) {
// cerr << a[i][j][0] << " = ";
// for (int k = 0; k < 2; ++k) {
// cerr << dp[i][j][k] << " ";
// }
// cerr << "\n";
// }
// cerr << "\n";
// }
// cerr << "\n";
ll res = 0;
for (int i = 0; i < (int)a[N].size(); ++i) {
for (int k = 0; k < 2; ++k) {
res = max(res, dp[N][i][k]);
}
}
// cerr << res << "\n";
return res;
}
