#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<int> vals;
vals.reserve(M + 2);
vals.push_back(0);
vals.push_back(N);
for (int i = 0; i < M; ++i) {
vals.push_back(Y[i]);
if (Y[i] + 1 <= N) vals.push_back(Y[i] + 1);
}
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int K = (int)vals.size();
vector<vector<pair<int,int>>> fidx(N);
for (int x = 0; x < N; ++x) {
for (auto [y, w] : fish[x]) {
int a = int(lower_bound(vals.begin(), vals.end(), y) - vals.begin());
fidx[x].push_back({a, w});
}
}
const long long NEG = -(1LL << 60);
auto score_col = [&](int x, int l, int c, int r) -> long long {
if (x < 0 || x >= N) return 0;
long long s = 0;
int hl = (l < 0 ? 0 : vals[l]);
int hc = vals[c];
int hr = (r < 0 ? 0 : vals[r]);
for (auto [yi, w] : fidx[x]) {
int y = vals[yi];
if (hc <= y && (hl > y || hr > y)) s += w;
}
return s;
};
if (N <= 3000 || K <= 400) {
vector<long long> dp(K * K, NEG), ndp(K * K, NEG);
for (int a = 0; a < K; ++a)
for (int b = 0; b < K; ++b)
dp[a * K + b] = 0;
for (int x = 1; x < N; ++x) {
fill(ndp.begin(), ndp.end(), NEG);
for (int a = 0; a < K; ++a) {
for (int b = 0; b < K; ++b) {
long long cur = dp[a * K + b];
if (cur == NEG) continue;
for (int c = 0; c < K; ++c) {
long long v = cur + score_col(x - 1, a, b, c);
long long &to = ndp[b * K + c];
if (v > to) to = v;
}
}
}
dp.swap(ndp);
}
long long ans = 0;
for (int a = 0; a < K; ++a)
for (int b = 0; b < K; ++b)
ans = max(ans, dp[a * K + b] + score_col(N - 1, a, b, -1));
return ans;
}
struct Fish { int x, y, w; };
vector<vector<Fish>> byY(N);
for (int i = 0; i < M; ++i) byY[Y[i]].push_back({X[i], Y[i], W[i]});
long long ans = 0;
vector<int> mid(N, 0);
for (int y = 0; y < N; ++y) {
for (auto &p : byY[y]) mid[p.x] += p.w;
long long take0 = 0, take1 = 0;
for (int x = 0; x < N; ++x) {
long long nt0 = max(take0, take1);
long long gain = 0;
if (x > 0) gain += mid[x - 1];
if (x + 1 < N) gain += mid[x + 1];
long long nt1 = take0 + gain;
take0 = nt0;
take1 = nt1;
}
ans = max(ans, max(take0, take1));
}
return ans;
}
