#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());
sort(fish[c].begin(), fish[c].end());
}
vector<long long> dp(vals[0].size(), 0), ndp;
for (int c = 1; c < N; ++c) {
int A = vals[c - 1].size();
int B = vals[c].size();
ndp.assign(B, LLONG_MIN / 4);
for (int bi = 0; bi < B; ++bi) {
int b = vals[c][bi];
long long best = LLONG_MIN / 4;
for (int ai = 0; ai < A; ++ai) {
int a = vals[c - 1][ai];
long long add = 0;
for (auto [y, w] : fish[c - 1]) {
if (a <= y && b > y) add += w;
}
best = max(best, dp[ai] + add);
}
ndp[bi] = best;
}
dp.swap(ndp);
}
long long ans = 0;
for (long long v : dp) ans = max(ans, v);
return ans;
}
