#include <bits/stdc++.h>
using namespace std;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
const long long NEG = -(1LL << 60);
vector<vector<pair<int, int>>> fish(N);
vector<vector<int>> coord(N);
for (int i = 0; i < N; ++i) {
coord[i].push_back(0);
coord[i].push_back(N);
}
for (int i = 0; i < M; ++i) {
int x = X[i], y = Y[i], t = y + 1;
fish[x].push_back({y, W[i]});
coord[x].push_back(t);
if (x > 0) coord[x - 1].push_back(t);
if (x + 1 < N) coord[x + 1].push_back(t);
}
for (int i = 0; i < N; ++i) {
sort(coord[i].begin(), coord[i].end());
coord[i].erase(unique(coord[i].begin(), coord[i].end()), coord[i].end());
sort(fish[i].begin(), fish[i].end());
}
vector<vector<int>> ys(N);
vector<vector<long long>> pref(N);
for (int i = 0; i < N; ++i) {
pref[i].push_back(0);
for (auto [y, w] : fish[i]) {
ys[i].push_back(y);
pref[i].push_back(pref[i].back() + w);
}
}
auto sum_less = [&](int col, int h) -> long long {
int p = lower_bound(ys[col].begin(), ys[col].end(), h) - ys[col].begin();
return pref[col][p];
};
vector<long long> A(coord[0].size(), 0), B(coord[0].size(), 0);
for (int i = 0; i + 1 < N; ++i) {
const vector<int>& cur = coord[i];
const vector<int>& nxt = coord[i + 1];
int K = (int)cur.size();
vector<long long> prefBest(K), suffBest(K);
long long maxB = NEG;
for (long long v : B) maxB = max(maxB, v);
for (int j = 0; j < K; ++j) {
long long val = A[j] - sum_less(i, cur[j]);
prefBest[j] = val;
if (j) prefBest[j] = max(prefBest[j], prefBest[j - 1]);
}
for (int j = K - 1; j >= 0; --j) {
long long val = B[j] + sum_less(i + 1, cur[j]);
suffBest[j] = val;
if (j + 1 < K) suffBest[j] = max(suffBest[j], suffBest[j + 1]);
}
vector<long long> nA(nxt.size(), NEG), nB(nxt.size(), NEG);
for (int j = 0; j < (int)nxt.size(); ++j) {
int h = nxt[j];
long long bestA = maxB;
int p = lower_bound(cur.begin(), cur.end(), h) - cur.begin();
if (p > 0) {
bestA = max(bestA, sum_less(i, h) + prefBest[p - 1]);
}
long long bestB = bestA;
int q = upper_bound(cur.begin(), cur.end(), h) - cur.begin();
if (q < K) {
bestB = max(bestB, suffBest[q] - sum_less(i + 1, h));
}
nA[j] = bestA;
nB[j] = bestB;
}
A.swap(nA);
B.swap(nB);
}
long long ans = 0;
for (long long v : B) ans = max(ans, v);
return ans;
}
