#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
struct AIB {
int n;
vll V;
AIB(int N) : n(N + 2), V(N + 2, 0) {}
void update(int p, ll v) {
++p;
while(p < n) {
V[p] = max(V[p], v);
p += p & -p;
}
}
ll query(int p) {
++p;
ll re = 0;
if(p < 0) return 0;
while(p) {
re = max(re, V[p]);
p -= p & -p;
}
return re;
}
};
struct maxSuf {
int n;
AIB A;
maxSuf(int N) : n(N), A(N) {}
void update(int p, ll v) { A.update(n - p - 1, v); }
ll query(int p) { return A.query(n - p - 1); }
};
ll max_weights(int n, int m, vi X, vi Y, vi W) {
vll DP0(m, 0), DP1(m, 0), MaTot(n, 0), Ma0(n, 0);
vector<vi> P(n);
for(int i = 0; i < m; ++i) {
P[X[i]].push_back(i);
}
AIB MP(n);
maxSuf MS(n);
for(int i = 0; i < n; ++i) {
sort(P[i].begin(), P[i].end(), [&](auto a, auto b) { return Y[a] > Y[b]; });
if(i > 0) {
for(auto it : P[i]) {
DP0[it] = (i > 1 ? MaTot[i - 2] : 0) + W[it];
DP0[it] = max(DP0[it], W[it] + MS.query(Y[it] + 1));
MS.update(Y[it], DP0[it]);
MaTot[i] = max(MaTot[i], DP0[it]);
Ma0[i] = max(Ma0[i], DP0[it]);
}
}
reverse(P[i].begin(), P[i].end());
if(i + 1 < n) {
for(auto it : P[i]) {
DP1[it] = max((i > 1 ? MaTot[i - 2] : 0), (i ? Ma0[i - 1] : 0)) + W[it];
DP1[it] = max(DP1[it], W[it] + MP.query(Y[it] - 1));
MP.update(Y[it], DP1[it]);
MaTot[i] = max(MaTot[i], DP1[it]);
}
}
if(i) {
MaTot[i] = max(MaTot[i], MaTot[i - 1]);
Ma0[i] = max(Ma0[i], Ma0[i - 1]);
}
}
return MaTot.back();
}
