#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define sz(v) ((int) v.size())
const int N = 1e5;
int dp1[N+5], dp2[N+5];
struct aint {
int n;
vector<ll> f;
aint (int _n) {
n = _n;
f.assign(n<<1, 0);
}
ll query(int l, int r) {
l += n; r += n+1;
ll res = 0;
for (;l < r; l>>=1, r>>=1) {
if (l&1) res = max(res, f[l++]);
if (r&1) res = max(res, f[--r]);
}
return res;
}
void upd(int x, ll v) {
x += n;
for (f[x] = max(f[x], v); x > 1; x>>=1) {
f[x>>1] = max(f[x], f[x^1]);
}
}
};
ll mv1[N+5], mv2[N+5];
ll
max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
vector<array<int, 3>> u(m), d(m);
for (int i = 0; i < m; ++i) {
u[i] = {x[i], y[i], i};
d[i] = {x[i], -y[i], i};
}
sort(u.begin(), u.end());
sort(d.begin(), d.end());
reverse(u.begin(), u.end());
reverse(d.begin(), d.end());
int up, dp;
up = dp = 0;
aint t1(n+5), t2(n+5);
ll t, v, i;
for (int x = n-1; x >= 0; --x) {
while (up < sz(u) && u[up][0] == x) {
if (x < n-1) {
i = u[up][2];
v = w[i];
t = t1.query(y[i]+1, n+2);
t = max({t, mv2[x+2], mv1[x+3]});
t1.upd(y[i], t+v);
}
++up;
}
while (dp < sz(d) && d[dp][0] == x) {
if (x > 0) {
i = d[dp][2];
v = w[i]; t = 0;
if (y[i])
t = t2.query(0, y[i]-1);
t = max({t, mv1[x+1], mv2[x+2]}) + v;
t2.upd(y[i], t);
}
++dp;
}
mv1[x] = mv1[x+1];
mv2[x] = mv2[x+1];
mv1[x] =t1.query(0, n+1);
mv2[x] =t2.query(0, n+1);
}
return max(t1.query(0, n+1), t2.query(0, n+1));
}
