#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 302020
typedef long long ll;
typedef pair<int, int> pii;
ll tdp[MAX]; // full dp
ll bdp[MAX]; // zero dp
ll sum[MAX];
vector<pii> locs[MAX];
struct bit {
int N;
bool rev;
vector<ll> tree;
bit(int N, bool rev) :N(N + 2), rev(rev) { tree = vector<ll>(N + 3, -1e18); }
void upd(int i, ll v) {
if (rev) i = N - i - 1;
i++;
while (i <= N) {
tree[i] = max(tree[i], v);
i += i & -i;
}
}
ll get(int i) {
if (rev) i = N - i - 1;
i++;
ll ans = -1e18;
while (i) {
ans = max(ans, tree[i]);
i -= i & -i;
}
return ans;
}
};
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
int i;
for (auto& v : X) v++;
for (auto& v : Y) v++;
for (i = 0; i < M; i++) locs[X[i]].emplace_back(Y[i], W[i]);
for (i = 1; i <= N; i++) if (locs[i].size()) {
sort(locs[i].begin(), locs[i].end());
for (auto& [_, v] : locs[i]) sum[i] += v;
}
bit fenu(N, false), fend(N, true);
fenu.upd(0, 0);
for (i = 0; i <= N; i++) tdp[i] = bdp[i] = -1e18;
for (i = 1; i <= N; i++) {
tdp[i] = tdp[i - 1];
bdp[i] = bdp[i - 1];
if (i > 2) fend.upd(N + 1, tdp[i - 2]);
if (i > 1) fenu.upd(0, bdp[i - 1]);
if (i > 1) fend.upd(N + 1, 0);
for (auto& [y, w] : locs[i]) fenu.upd(y, fenu.get(y - 1) + w);
tdp[i] = max(tdp[i], fenu.get(N + 1));
for (int j = (int)locs[i].size() - 1; j >= 0; j--) {
ll y = locs[i][j].first;
ll w = locs[i][j].second;
fend.upd(y, fend.get(y + 1) + w);
}
bdp[i] = max(bdp[i], fend.get(0));
if (i > 2) tdp[i] = max(tdp[i], sum[i] + tdp[i - 2]);
}
ll ans = fend.get(0);
for (i = 1; i < N; i++) ans = max(ans, tdp[i]);
for (i = 1; i <= N; i++) ans = max(ans, bdp[i]);
return ans;
}
