#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
map<int, ll> v[N], h[N];
vector<ll> f[N];
vector<int> pos[N];
vector<pair<int, ll>> S[N];
ll s(int p, int u) {
if (auto it = lower_bound(S[p].begin(), S[p].end(), pair(u + 1, (ll) -1e18)); it != S[p].begin()) return prev(it)->second;
return 0;
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
for (int i = 0; i < m; ++i)
v[x[i] + 1][y[i] + 1] += w[i], pos[x[i] + 1].push_back(y[i]);
for (int i = 1; i <= n; ++i) {
sort(pos[i].begin(), pos[i].end()), pos[i].push_back(n);
ll c = 0;
for (auto [p, v]: v[i])
c += v, S[i].emplace_back(p, c);
}
for (int j: pos[1])
h[1][j] = 0;
f[1].resize(pos[1].size());
for (int i = 2; i <= n; ++i) {
f[i].resize(pos[i].size());
auto g = pos[i - 1].size() - 1;
ll ma = -1e18;
for (int j = (int) pos[i].size() - 1; j >= 0; --j) {
while (~g && pos[i - 1][g] >= pos[i][j])
ma = max(ma, f[i - 1][g] + s(i, pos[i - 1][g])), --g;
f[i][j] = ma - s(i, pos[i][j]);
}
auto l = h[i - 1].begin();
ma = -1e18;
for (int j = 0; j < pos[i].size(); ++j) {
while (l != h[i - 1].end() && l->first <= pos[i][j])
ma = max(ma, l->second - s(i - 1, l->first)), ++l;
f[i][j] = max(f[i][j], h[i][pos[i][j]] = ma + s(i - 1, pos[i][j]));
}
for (int j = 0; j < pos[i - 1].size(); ++j)
h[i][pos[i - 1][j]] = max(h[i][pos[i - 1][j]], f[i - 1][j] + s(i, pos[i - 1][j]));
}
ll mx = 0;
for (ll v: f[n])
mx = max(mx, v);
return mx;
}
