#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);
vector<vector<int>> vals(N);
for (int i = 0; i < M; ++i) {
fish[X[i]].push_back({Y[i], W[i]});
vals[X[i]].push_back(Y[i]);
vals[X[i]].push_back(Y[i] + 1);
if (X[i] > 0) vals[X[i] - 1].push_back(Y[i] + 1);
if (X[i] + 1 < N) vals[X[i] + 1].push_back(Y[i] + 1);
}
for (int c = 0; c < N; ++c) {
vals[c].push_back(0);
vals[c].push_back(N);
sort(vals[c].begin(), vals[c].end());
vals[c].erase(unique(vals[c].begin(), vals[c].end()), vals[c].end());
}
const long long NEG = -(1LL << 60);
auto edge_value = [&](int col, int hl, int hr) -> long long {
if (col < 0 || col >= N) return 0;
long long res = 0;
for (auto [y, w] : fish[col]) {
if (hr <= y && hl > y) res += w;
}
return res;
};
vector<long long> dp(vals[0].size(), 0), ndp;
for (int i = 1; i < N; ++i) {
int L = (int)vals[i - 1].size();
int R = (int)vals[i].size();
ndp.assign(R, NEG);
vector<long long> best_prefix(R, NEG);
for (int a = 0; a < L; ++a) {
int h_prev = vals[i - 1][a];
long long base = dp[a] + edge_value(i - 2, 0, 0);
(void)base;
for (int b = 0; b < R; ++b) {
int h_cur = vals[i][b];
long long add = 0;
for (auto [y, w] : fish[i - 1]) {
if (h_prev <= y && h_cur > y) add += w;
}
ndp[b] = max(ndp[b], dp[a] + add);
}
}
dp.swap(ndp);
}
long long ans = 0;
for (int a = 0; a < (int)vals[N - 1].size(); ++a) {
ans = max(ans, dp[a]);
}
vector<unordered_map<int, int>> id(N);
for (int i = 0; i < N; ++i) {
id[i].reserve(vals[i].size() * 2);
for (int j = 0; j < (int)vals[i].size(); ++j) id[i][vals[i][j]] = j;
}
vector<vector<long long>> left_gain(N), right_gain(N);
for (int c = 0; c < N; ++c) {
left_gain[c].assign(vals[c].size(), 0);
right_gain[c].assign(vals[c].size(), 0);
for (int j = 0; j < (int)vals[c].size(); ++j) {
int h = vals[c][j];
if (c > 0) {
for (auto [y, w] : fish[c - 1]) {
if (h > y) left_gain[c][j] += w;
}
}
if (c + 1 < N) {
for (auto [y, w] : fish[c + 1]) {
if (h > y) right_gain[c][j] += w;
}
}
}
}
vector<vector<long long>> dp2(N);
dp2[0].assign(vals[0].size(), 0);
for (int j = 0; j < (int)vals[0].size(); ++j) {
int h0 = vals[0][j];
long long s = 0;
for (auto [y, w] : fish[1 < N ? 1 : 0]) {
if (N > 1 && h0 > y) s += w;
}
dp2[0][j] = s;
}
for (int i = 1; i < N; ++i) {
dp2[i].assign(vals[i].size(), NEG);
for (int a = 0; a < (int)vals[i - 1].size(); ++a) {
int hp = vals[i - 1][a];
for (int b = 0; b < (int)vals[i].size(); ++b) {
int hc = vals[i][b];
long long add = 0;
for (auto [y, w] : fish[i - 1]) {
if (hp <= y && hc > y) add += w;
if (hp <= y && i >= 2 && vals[i - 2][0] > y) add += 0;
}
for (auto [y, w] : fish[i + 1 < N ? i + 1 : i]) {
if (i + 1 < N && hc > y) add += w;
}
dp2[i][b] = max(dp2[i][b], dp2[i - 1][a] + add);
}
}
}
return ans;
}
