#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
const int N = 1e5 + 5;
namespace sub1 {
bool check(int m, vector <array <int, 3>> fishes) {
REP(i, m) {
if (fishes[i][0] & 1) return false;
}
return true;
}
long long solve(int m, vector <array <int, 3>> fishes) {
//assert(1 == 0);
long long ans = 0;
REP(i, m) ans += fishes[i][2];
return ans;
}
}
namespace sub2 {
bool check(int m, vector <array <int, 3>> fishes) {
REP(i, m) if (fishes[i][0] > 1) return false;
return true;
}
long long solve(int n, int m, vector <array <int, 3>> fishes) {
//assert(1 == 0);
if (n == 2) {
long long ans[2] = {0};
REP(i, m) ans[fishes[i][0]] += fishes[i][2];
return max(ans[0], ans[1]);
}
vector <long long> sum[2];
REP(i, 2) sum[i].resize(n + 7, 0);
REP(i, m) sum[fishes[i][0]][fishes[i][1]] += fishes[i][2];
FOR(i, 1, n - 1) REP(j, 2) sum[j][i] = sum[j][i - 1] + sum[j][i];
long long ans = sum[1][n - 1];
REP(i, n) maximize(ans, sum[0][i] + sum[1][n - 1] - sum[1][i]);
return ans;
}
}
namespace sub3 {
bool check(int m, vector <array <int, 3>> fishes) {
REP(i, m) if (fishes[i][1] != 0) return false;
return true;
}
int cost[N];
long long dp[N];
long long solve(int n, int m, vector <array <int, 3>> fishes) {
REP(i, m) cost[fishes[i][0] + 1] = fishes[i][2];
FOR(i, 1, n) {
maximize(dp[i], dp[i - 1]);
if (i >= 2) maximize(dp[i], dp[i - 2] + cost[i - 1]);
if (i > 3) maximize(dp[i], dp[i - 3] + cost[i - 1] + cost[i - 2]);
}
long long ans = 0;
FOR(i, 1, n) {
dp[i] = dp[i] + cost[i + 1];
maximize(ans, dp[i]);
}
return ans;
}
}
const long long INF = 1e18 + 7;
namespace sub6 {
vector <int> coor[N];
vector <long long> f[N], g[N];
vector <pair <int, long long>> sum[N];
const int M = 3e3 + 5;
long long sum2[M][M];
long long get_sum(int n, int i, int x) {
if (n <= 3e3) return sum2[i][x];
if (sum[i].size() == 0 || x < sum[i][0].first) return 0;
if (sum[i].back().first <= x) return sum[i].back().second;
int pos = upper_bound(ALL(sum[i]), make_pair(x, INF)) - sum[i].begin() - 1;
if (pos == -1) return 0;
return sum[i][pos].second;
}
long long solve(int n, int m, vector <array <int, 3>> fishes) {
REP(i, m) {
if (fishes[i][0] + 1 > 1) coor[fishes[i][0]].push_back(fishes[i][1] + 1);
if (fishes[i][0] + 1 < n) coor[fishes[i][0] + 2].push_back(fishes[i][1] + 1);
if (n <= 3e3) sum2[fishes[i][0] + 1][fishes[i][1] + 1] = fishes[i][2];
sum[fishes[i][0] + 1].push_back({fishes[i][1] + 1, fishes[i][2]});
}
if (n <= 3e3) {
FOR(i, 1, n) FOR(j, 1, n) sum2[i][j] += sum2[i][j - 1];
}
FOR(i, 1, n) {
coor[i].push_back(0);
sort (ALL(coor[i]));
coor[i].erase(unique(ALL(coor[i])), coor[i].end());
f[i].resize(coor[i].size() + 5, -1);
g[i].resize(coor[i].size() + 5, -1);
sort (ALL(sum[i]));
FOR(j, 1, (int) sum[i].size() - 1) sum[i][j].second += sum[i][j - 1].second;
}
// f : roi
// g : chua
REP(i, coor[1].size()) g[1][i] = 0;
FOR(i, 2, n) {
REP(k, coor[i - 1].size()) if (f[i - 1][k] != -1 || g[i - 1][k] != -1) {
REP(j, coor[i].size()) if (coor[i - 1][k] <= coor[i][j]) {
// f
if (f[i - 1][k] != -1) maximize(g[i][j], f[i - 1][k]);
// g
if (g[i - 1][k] != -1) {
long long R = get_sum(n, i - 1, coor[i][j]);
long long L = get_sum(n, i - 1, coor[i - 1][k]);
maximize(g[i][j], g[i - 1][k] + R - L);
}
}
else {
// update f
maximize(f[i][j], max(f[i - 1][k], g[i - 1][k]) + get_sum(n, i, coor[i - 1][k]) - get_sum(n, i, coor[i][j]));
// update g
maximize(g[i][j], max(f[i - 1][k], g[i - 1][k]));
}
}
if (i > 2) {
REP(k, coor[i - 2].size()) if (f[i - 2][k] != -1 || g[i - 2][k] != -1) {
REP(j, coor[i].size()) {
maximize(g[i][j], max(f[i - 2][k], g[i - 2][k]) + get_sum(n, i - 1, max(coor[i - 2][k], coor[i][j])));
}
}
}
if (i > 3) {
REP(k, coor[i - 3].size()) if (f[i - 3][k] != -1 || g[i - 3][k] != -1) {
REP(j, coor[i].size()) {
maximize(g[i][j], max(f[i - 3][k], g[i - 3][k]) + get_sum(n, i - 1, coor[i][j]) + get_sum(n, i - 2, coor[i - 3][k]));
}
}
}
}
long long ans = 0;
FOR(i, 1, n) REP(j, coor[i].size()) maximize(ans, max(f[i][j], g[i][j]) + get_sum(n, i + 1, coor[i][j]));
return ans;
}
};
long long max_weights(int n, int m, vector <int> X, vector <int> Y, vector <int> W) {
vector <array <int, 3>> fishes;
fishes.resize(m + 7);
REP(i, m) fishes[i] = {X[i], Y[i], W[i]};
if (sub1::check(m, fishes)) return sub1::solve(m, fishes);
else if (sub2::check(m, fishes)) return sub2::solve(n, m, fishes);
else if (sub3::check(m, fishes)) return sub3::solve(n, m, fishes);
else return sub6::solve(n, m, fishes);
return 0;
}
