#include <bits/stdc++.h>
using namespace std;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<pair<int,int>>> fish(N);
for (int i = 0; i < M; ++i) fish[Y[i]].push_back({X[i], W[i]});
for (int c = 0; c < N; ++c) {
sort(fish[c].begin(), fish[c].end());
}
auto pref_sum = [&](int c, int h) -> long long {
long long s = 0;
for (auto [x, w] : fish[c]) {
if (x < h) s += w;
else break;
}
return s;
};
vector<int> cols;
cols.reserve(N);
for (int c = 0; c < N; ++c) {
if (!fish[c].empty()) {
if (cols.empty() || cols.back() != c - 1) cols.push_back(c - 1);
cols.push_back(c);
if (c + 1 < N) cols.push_back(c + 1);
}
}
sort(cols.begin(), cols.end());
cols.erase(unique(cols.begin(), cols.end()), cols.end());
unordered_map<int, int> id;
id.reserve(cols.size() * 2 + 1);
for (int i = 0; i < (int)cols.size(); ++i) id[cols[i]] = i;
vector<vector<int>> hs(cols.size());
for (int i = 0; i < (int)cols.size(); ++i) {
int c = cols[i];
hs[i].push_back(0);
hs[i].push_back(N);
for (int dc = -1; dc <= 1; ++dc) {
int nc = c + dc;
if (0 <= nc && nc < N) {
for (auto [x, w] : fish[nc]) {
hs[i].push_back(x);
hs[i].push_back(x + 1);
}
}
}
sort(hs[i].begin(), hs[i].end());
hs[i].erase(unique(hs[i].begin(), hs[i].end()), hs[i].end());
}
const long long NEG = -(1LL << 60);
vector<long long> dp_prev(1, 0);
vector<int> h_prev(1, 0);
int prev_col = -2;
for (int idx = 0; idx < (int)cols.size(); ++idx) {
int c = cols[idx];
vector<int>& cur_h = hs[idx];
vector<long long> dp_cur(cur_h.size(), NEG);
if (c != prev_col + 1) {
h_prev.assign(1, 0);
dp_prev.assign(1, 0);
}
for (int a = 0; a < (int)h_prev.size(); ++a) {
for (int b = 0; b < (int)cur_h.size(); ++b) {
long long gain = 0;
int mid_col = c - 1;
if (0 <= mid_col && mid_col < N) {
int own = h_prev[a];
int adj = cur_h[b];
if (adj > own) gain += pref_sum(mid_col, adj) - pref_sum(mid_col, own);
}
dp_cur[b] = max(dp_cur[b], dp_prev[a] + gain);
}
}
dp_prev.swap(dp_cur);
h_prev = cur_h;
prev_col = c;
}
long long ans = 0;
for (int a = 0; a < (int)h_prev.size(); ++a) {
long long cur = dp_prev[a];
int last_col = prev_col;
if (0 <= last_col && last_col < N) {
int own = h_prev[a];
int adj = 0;
if (adj > own) cur += pref_sum(last_col, adj) - pref_sum(last_col, own);
}
ans = max(ans, cur);
}
return ans;
}
