#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const int64_t inf = 1e18;
class segtree_t {
public:
segtree_t *left, *right;
int l, r, m;
int64_t val;
segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(-inf) {
if (l == r) return;
left = new segtree_t(l, m);
right = new segtree_t(m + 1, r);
}
void Update(int s, int t, int64_t x) {
if (r < s || l > t) return;
if (s <= l && r <= t) {
val = max(val, x);
return;
}
left->Update(s, t, x);
right->Update(s, t, x);
}
int64_t Get(int p) {
if (l == r) return val;
if (p <= m) return max(val, left->Get(p));
return max(val, right->Get(p));
}
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<int64_t> sum(N);
vector<int> aback(N);
for (int i = 0; i < M; i++) {
sum[X[i]] += W[i];
if (Y[i] == N - 1) aback[X[i]] = W[i];
}
const int64_t inf = 1e18;
vector<vector<pair<int, int>>> event(N);
for (int i = 0; i < M; i++) {
event[X[i]].emplace_back(Y[i], W[i]);
}
for (int i = 0; i < N; i++) {
event[i].emplace_back(0, 0);
event[i].emplace_back(N - 2, 0);
sort(event[i].begin(), event[i].end());
}
segtree_t *tree0 = new segtree_t(0, N);
segtree_t *tree1 = new segtree_t(0, N);
tree0->Update(0, N, 0);
tree1->Update(N, N, 0);
for (int i = 0; i < N; i++) {
if (i + 1 < N) {
for (auto [y, w] : event[i]) {
tree0->Update(y + 1, N, tree0->Get(y) + w);
}
}
reverse(event[i].begin(), event[i].end());
if (i > 0) {
for (auto [y, w] : event[i]) {
if (y == N - 1) continue;
tree1->Update(0, y, tree1->Get(y + 1) + w);
}
}
if (i == 1) tree0->Update(0, 0, sum[0]);
if (i + 2 < N) tree0->Update(0, 0, tree1->Get(0));
if (i == N - 1) break;
int64_t dpN1 = tree1->Get(N);
int64_t dp01 = tree1->Get(0);
tree1->Update(N, N, max(tree0->Get(N), tree0->Get(0)));
if (i + 1 == N - 1) tree0->Update(N, N, tree0->Get(0) + sum[N - 1]);
tree1->Update(N - 1, N - 1, dpN1 + aback[i + 1]);
tree0->Update(0, 0, dp01);
}
return max(tree1->Get(0), max(tree0->Get(N), tree1->Get(N)));
}
