#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct fish {
int y, w;
bool operator < (const fish &b) const {
return y < b.y;
}
};
const int maxn = 1e5 + 5, maxN = 4e5 + 5, maxm = 5e5 + 5, INF = 1e16;
int n, m;
vector<fish> a[maxn];
int seg[maxN][2];
void build(int id, int l, int r, int j) {
if (l == r) {
if (l == 0 && j == 1) seg[id][j] = 0;
else seg[id][j] = -INF;
return;
}
int mid = (l+r)/2;
build(id*2, l, mid, j); build(id*2+1, mid+1, r, j);
seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
void update(int id, int l, int r, int target, int val, int j) {
if (r < target || target < l) return;
if (l == r) {
seg[id][j] = max(val, seg[id][j]);
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, target, val, j); update(id*2+1, mid+1, r, target, val, j);
seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
int qry(int id, int l, int r, int findl, int findr, int j) {
if (r < findl || findr < l) return -INF;
if (findl <= l && r <= findr) return seg[id][j];
int mid = (l+r)/2;
return max(qry(id*2, l, mid, findl, findr, j), qry(id*2+1, mid+1, r, findl, findr, j));
}
long long max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y,
vector<int32_t> W) {
n = N, m = M;
for (int i=0;i<m;i++) a[X[i] + 1].push_back({Y[i] + 1, W[i]});
for (int i=1;i<=n+1;i++) {
a[i].push_back({0, 0});
if (i != n+1) a[i].push_back({n+1, 0});
sort(a[i].begin(), a[i].end());
}
build(1, 0, n+1, 0);
build(1, 0, n+1, 1);
for (int i=1;i<=n+1;i++) {
int sz = a[i].size();
int nxt = qry(1, 0, n+1, 0, n+1, 1);
for (auto [y, w]:a[i]) {
int cur = qry(1, 0, n+1, 0, y-1, 1) + w;
update(1, 0, n+1, y, cur, 1);
// cout << i << " " << y << endl;
// cout << i << " " << y << " 1 " << cur << endl;
// cout << seg[y][1] << endl;
}
reverse(a[i].begin(), a[i].end());
for (auto [y, w]:a[i]) {
int cur = qry(1, 0, n+1, y+1, n+1, 0) + w;
update(1, 0, n+1, y, cur, 0);
// if (i == 3 && y == 5 || y == 6) cout << y << " " << cur << endl;
// cout << i << " " << y << " 0 " << cur << endl;
// cout << seg[y][0] << endl;
}
update(1, 0, n+1, n+1, nxt, 0);
update(1, 0, n+1, 0, qry(1, 0, n+1, 0, 0, 0), 1);
// cout << i << endl;
// for (int j=0;j<=n+1;j++) cout << seg[j][0] << " "; cout << endl;
// for (int j=0;j<=n+1;j++) cout << seg[j][1] << " "; cout << endl;
}
return qry(1, 0, n+1, 0, 0, 0);
}
