#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
const int inf = 1e16;
vector<pair<int, int>> item[100002];
map<int, int> mp[2][100002];
long long max_weights(i32 N, i32 M, std::vector<i32> X, std::vector<i32> Y,
std::vector<i32> W) {
for (int i = 0; i < M; i++) {
X[i]++, Y[i]++;
item[X[i]].push_back({Y[i], W[i]});
}
for (int i = 1; i <= N; i++) {
sort(item[i].begin(), item[i].end());
for (int j = 1; j < item[i].size(); j++) item[i][j].second += item[i][j - 1].second;
}
int ans = 0;
mp[0][0][0] = 0;
for (int i = 1; i <= N; i++) mp[0][0][i] = mp[1][0][i] = -inf;
for (int i = 1; i <= N; i++) {
vector<int> cand = {0, N};
for (int j = 0; j < item[i].size(); j++) cand.push_back(item[i][j].first - 1);
auto que = [&] (int i, int j) {
int mins = 0;
if (!item[i].empty() && item[i].front().first <= j) {
auto it = lower_bound(item[i].begin(), item[i].end(), make_pair(j+1, 0LL));
--it;
mins = (*it).second;
}
return mins;
};
vector<pair<int, int>> t0p, t1p;
map<int, int> c0p = mp[0][i-1], c1p = mp[1][i-1];
for (auto& [key, val] : mp[0][i-1]) {
val += que(i, key);
t0p.push_back({key, val});
}
for (auto& [key, val] : mp[1][i-1]) {
val += que(i, key);
t1p.push_back({key, val});
}
for (int j = (int) t0p.size() - 2; j >= 0; j--) {
mp[0][i-1][t0p[j].first] = max(mp[0][i-1][t0p[j+1].first], t0p[j].second);
}
for (int j = (int) t1p.size() - 2; j >= 0; j--) {
mp[1][i-1][t1p[j].first] = max(mp[1][i-1][t1p[j+1].first], t1p[j].second);
}
for (auto& j : cand) {
int bruh = 0;
auto it = mp[0][i-1].lower_bound(j);
if (it != mp[0][i-1].end()) bruh = it->second;
auto it2 = mp[1][i-1].lower_bound(j);
if (it2 != mp[1][i-1].end()) bruh = max(bruh, it2->second);
bruh -= que(i, j);
mp[1][i][j] = bruh;
ans = max(ans, bruh);
}
mp[0][i-1] = c0p;
mp[1][i-1] = c1p;
t0p.clear(), t1p.clear();
for (auto& [key, val] : mp[0][i-1]) {
val -= que(i-1, key);
t0p.push_back({key, val});
}
for (int j = 1; j < t0p.size(); j++) {
mp[0][i-1][t0p[j].first] = max(mp[0][i-1][t0p[j-1].first], t0p[j].second);
}
for (auto& j : cand) {
int bruh = 0;
if (!mp[0][i-1].empty() && mp[0][i-1].begin()->first <= j) {
auto it = --mp[0][i-1].upper_bound(j);
bruh = max(bruh, it->second);
}
if (i >= 2) {
if (mp[1][i-2].count(0)) bruh = max(bruh, mp[1][i-2][0]);
}
bruh += que(i-1, j);
mp[0][i][j] = bruh;
ans = max(ans, bruh);
}
mp[0][i-1] = c0p;
if (i >= 2) {
vector<pair<int, int>> t2p;
for (auto& [key, val] : mp[0][i-2]) {
t2p.push_back({key, val});
}
for (int j = 1; j < t2p.size(); j++) {
mp[0][i-2][t2p[j].first] = max(mp[0][i-2][t2p[j-1].first], t2p[j].second);
}
for (auto& j : cand) {
int bruh = que(i-1, j);
if (!mp[0][i-2].empty() && mp[0][i-2].begin()->first <= j) {
auto it = --mp[0][i-2].upper_bound(j);
bruh += it->second;
}
mp[0][i][j] = max(mp[0][i][j], bruh);
ans = max(ans, bruh);
}
}
}
return ans;
}
