#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
struct fish {
int x, y, w;
};
int M, N;
vector<fish> f;
vector<int> idxAct;
vector<vector<long long>> prefAct;
vector<long long> memo;
long long prefixAct(int n, int l, int r) {
if (r < l) return 0;
if (l <= 0) return prefAct[n][r];
return prefAct[n][r] - prefAct[n][l-1];
}
bool comp2 (const fish &a, const fish &b) {
if (a.x < b.x) return true;
if (a.x == b.x && a.y < b.y) return true;
if (a.x == b.x && a.y == b.y && a.w < b.w) return true;
return false;
}
long long dp(int i) {
if (i >= M) return 0;
if (memo[i] != -1) return memo[i];
long long notake = dp(i + 1);
int index = lower_bound(f.begin(), f.end(), fish({f[i].x + 1, -1, -1}), comp2) - f.begin();
long long takeLeft = dp(index) + prefixAct(f[i].x, 0, idxAct[i]);
long long takeRight = dp(index) + prefixAct(f[i].x, 0, idxAct[i]);
int index2 = lower_bound(f.begin(), f.end(), fish({f[i].x + 1, f[i].y + 1, -1}), comp2) - f.begin() - 1;
if (f[index2].x == f[i].x+1) takeRight -= prefixAct(f[i].x+1, 0, idxAct[index2]);
int index3 = lower_bound(f.begin(), f.end(), fish({f[i].x - 1, f[i].y + 1, -1}), comp2) - f.begin() - 1;
if (f[index3].x == f[i].x-1) takeLeft -= prefixAct(f[i].x - 1, 0, idxAct[index3]);
if (!f[i].x) takeLeft = 0;
if (f[i]. x >= N-1) takeRight = 0;
return memo[i] = max(notake, max(takeLeft, takeRight));
}
long long max_weights(int NN, int MM, vector<int> X, vector<int> Y,vector<int> W) {
ios::sync_with_stdio(false);
M = MM, N = NN;
f.resize(M);
for (int i = 0; i < M; i++) f[i] = fish({X[i], Y[i], W[i]});
sort(f.begin(), f.end(), comp2);
prefAct.resize(N); idxAct.resize(M);
for (int i = 0; i < M; i++) {
idxAct[i] = (int)(prefAct[f[i].x].size());
prefAct[f[i].x].push_back(f[i].w);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < int(prefAct[i].size()); j++) {
if (j) prefAct[i][j] += prefAct[i][j-1];
}
}
memo.resize(M,-1);
return dp(0);
}
