#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[X[i]].push_back({Y[i], W[i]});
vector<vector<int>> ys(N);
vector<vector<long long>> pref(N);
vector<int> allY;
allY.reserve(M + 1);
allY.push_back(0);
for (int c = 0; c < N; ++c) {
auto &v = fish[c];
sort(v.begin(), v.end());
for (int i = 0; i < (int)v.size();) {
int y = v[i].first;
long long s = 0;
while (i < (int)v.size() && v[i].first == y) s += v[i++].second;
ys[c].push_back(y);
pref[c].push_back(s);
allY.push_back(y);
allY.push_back(y + 1);
}
for (int i = 1; i < (int)pref[c].size(); ++i) pref[c][i] += pref[c][i - 1];
}
sort(allY.begin(), allY.end());
allY.erase(unique(allY.begin(), allY.end()), allY.end());
auto col_sum = [&](int c, int lo, int hi) -> long long {
if (c < 0 || c >= N || lo >= hi) return 0;
auto &v = ys[c];
auto &p = pref[c];
int l = lower_bound(v.begin(), v.end(), lo) - v.begin();
int r = lower_bound(v.begin(), v.end(), hi) - v.begin();
if (l >= r) return 0;
return p[r - 1] - (l ? p[l - 1] : 0);
};
const long long NEG = -(1LL << 60);
int K = (int)allY.size();
vector<long long> dp_prev(K, 0), dp_cur(K, NEG);
for (int i = 0; i < N; ++i) {
vector<long long> leftGain(K), rightGain(K), selfLose(K);
for (int a = 0; a < K; ++a) {
int h = allY[a];
leftGain[a] = col_sum(i - 1, 0, h);
rightGain[a] = col_sum(i + 1, 0, h);
selfLose[a] = col_sum(i, 0, h);
}
vector<long long> bestPrefix(K, NEG), bestSuffix(K, NEG);
for (int a = 0; a < K; ++a) {
long long v = dp_prev[a] + rightGain[a] - selfLose[a];
bestPrefix[a] = max(a ? bestPrefix[a - 1] : NEG, v);
}
for (int a = K - 1; a >= 0; --a) {
long long v = dp_prev[a] + rightGain[a];
bestSuffix[a] = max(a + 1 < K ? bestSuffix[a + 1] : NEG, v);
}
for (int b = 0; b < K; ++b) {
dp_cur[b] = max(bestPrefix[b] + leftGain[b], bestSuffix[b] - selfLose[b] + leftGain[b]);
}
dp_prev.swap(dp_cur);
}
return *max_element(dp_prev.begin(), dp_prev.end());
}
