#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n;
vector<pii> P[100005];
struct segtree {
ll seg[1 << 18];
void init() {
memset(seg, 0xcf, sizeof(seg));
}
void update(int i, int s, int e, int x, int y, ll v) {
if (e < x || y < s) return;
if (x <= s && e <= y) {
seg[i] = max(seg[i], v);
return;
}
int m = (s + e) / 2;
update(i + i, s, m, x, y, v);
update(i + i + 1, m + 1, e, x, y, v);
}
ll query(int i, int s, int e, int x) {
if (s == e) return seg[i];
int m = (s + e) / 2;
if (x <= m) return max(seg[i], query(i + i, s, m, x));
return max(seg[i], query(i + i + 1, m + 1, e, x));
}
} up, dn;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N;
for (int i = 0; i < M; ++i) {
P[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
}
ll p = 0;
dn.init();
for (int i = 1; i <= n; ++i) {
ll sum = 0;
sort(P[i].begin(), P[i].end());
for (auto [j, v] : P[i]) {
sum += v;
up.update(1, 0, n + 1, j + 1, n + 1, up.query(1, 0, n + 1, j) + v);
}
reverse(P[i].begin(), P[i].end());
for (auto [j, v] : P[i]) {
dn.update(1, 0, n + 1, 0, j - 1, dn.query(1, 0, n + 1, j) + v);
}
ll u = up.query(1, 0, n + 1, n + 1);
ll d = dn.query(1, 0, n + 1, 0);
up.update(1, 0, n + 1, 0, n + 1, d);
dn.update(1, 0, n + 1, 0, n + 1, p);
p = max(u, d);
}
return dn.query(1, 0, n + 1, 0);
}
