/**
* Author: Nicholas Winschel
* Created: 05.09.2023 22:40:58
**/
// screw this problem man. had [most of] the main insights almost immediately, couldn't work out the implementation details (i am allergic to 2 ptrs)
// for over 2 days. just gave up, checked online and someone had a 50 line solution that did pretty much exactly what I expected
// i'm not mad, you're mad.
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
#include "fish.h"
// THIS IMPL IS NOT ORIGINAL.
const int MAXN = 1e5+5;
const ll inf = 1e18;
map<int, ll> c[MAXN], blo[MAXN];
vl dp[MAXN];
vi pos[MAXN];
V<pair<int,ll>> pre[MAXN];
ll lsum(int ind, int ub) {
auto i = lower_bound(pre[ind].begin(),pre[ind].end(), pair<int,ll>{ub+1, -inf});
if (i == pre[ind].begin()) return 0;
return (--i)->second;
}
long long max_weights(int N, int M, vi X, vi Y, vi W) {
for (int i = 0; i < M; i++)
c[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 tot = 0;
for (auto [po, val] : c[i]) tot += val, pre[i].emplace_back(po,tot);
}
for (int j : pos[1]) blo[1][j]=0;
dp[1]=vl(sz(pos[1]));
for (int i = 2; i <= N; i++) {
dp[i].resize(sz(pos[i]));
// handle case where left is greater
int l = pos[i-1].size()-1;
ll bsf = -inf;
for (int r = sz(pos[i]) - 1; r >= 0; r--) {
while (l >= 0 && pos[i-1][l] >= pos[i][r])
bsf = max(bsf, dp[i-1][l] + lsum(i, pos[i-1][l])),--l;
dp[i][r]=bsf-lsum(i,pos[i][r]);
}
auto it = blo[i-1].begin();
bsf=-inf;
for (int r = 0; r < sz(pos[i]); r++) {
while (it != blo[i-1].end() && it->f <= pos[i][r])
bsf = max(bsf, it->s - lsum(i-1, it->f)),++it;
dp[i][r]=max(dp[i][r],
blo[i][pos[i][r]]= bsf + lsum(i-1,pos[i][r])); // why does this work again?
}
for (int j = 0; j < sz(pos[i-1]); j++)
blo[i][pos[i-1][j]] = max(blo[i][pos[i-1][j]], dp[i-1][j] + lsum(i,pos[i-1][j])); // OH
}
ll ret = 0;
for (ll v : dp[N]) ret = max(ret, v);
return ret;
}
