#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;
vector<pair<int, int>> col[maxN];
vector<long long> dp_down[maxN];
vector<long long> dp_up[maxN];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int i = 0; i < M; i++) {
col[X[i]].emplace_back(Y[i], W[i]);
}
for (int i = 0; i < N; i++) {
col[i].emplace_back(-1, 0);
col[i].emplace_back(N, 0);
sort(col[i].begin(), col[i].end());
dp_down[i].resize(col[i].size(), (i ? -inf : 0));
dp_up[i].resize(col[i].size(), (i ? -inf: 0));
}
for (int i = 1; i < N; i++) {
int prv_sz = col[i - 1].size();
int cur_sz = col[i].size();
int pt = cur_sz - 1;
for (int j = prv_sz - 1; j >= 0; j--) {
while (col[i][pt].first > col[i - 1][j].first) {
pt--;
}
dp_down[i][pt] = max(dp_down[i][pt], max(dp_up[i - 1][j], dp_down[i - 1][j]) + (col[i][pt].first < col[i - 1][j].first ? col[i][pt].second : 0));
}
for (int j = cur_sz - 2; j >= 0; j--) {
dp_down[i][j] = max(dp_down[i][j], dp_down[i][j + 1] + col[i][j].second);
}
long long max_up = -inf;
long long max_down = -inf;
pt = -1;
for (int j = 0; j < cur_sz; j++) {
while (pt + 1 < prv_sz && col[i - 1][pt + 1].first < col[i][j].first) {
max_up = max(max_up, dp_up[i - 1][pt + 1]) + col[i - 1][pt + 1].second;
max_down = max(max_down, dp_down[i - 1][pt + 1]);
pt++;
}
if (pt + 1 < prv_sz && col[i - 1][pt + 1].first == col[i][j].first) {
dp_up[i][j] = max(dp_up[i][j], dp_up[i - 1][pt + 1]);
dp_up[i][j] = max(dp_up[i][j], dp_down[i - 1][pt + 1]);
}
dp_up[i][j] = max(dp_up[i][j], max_up);
dp_up[i][j] = max(dp_up[i][j], max_down);
}
}
long long res = 0;
for (int i = 0; i < (int)col[N - 1].size(); i++) {
res = max(res, dp_up[N - 1][i]);
res = max(res, dp_down[N - 1][i]);
}
return res;
}
