#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
using vi = vector <int>;
// dp[i][j] = max grams caught if caught catfish until j from column i-1
// pier worth extending up to every catfish or until the end (O(n+m) optimal maximal piers)
const ll MAXN = 1E5+16, INF = ll(1E18)+16;
ll dp[MAXN];
vii ccs[MAXN];
ll max_weights (int n, int m, vi vx, vi vy, vi vw) {
for (ll i = 0; i < m; i++)
ccs[vx[i]].push_back({ vy[i]+1, vw[i] });
for (ll x = 0; x < n; x++) {
sort(ccs[x].begin(), ccs[x].end());
ccs[x].insert(ccs[x].begin(), ii{ -1, 0 });
// ps[x].push_back(0);
ll acc = 0;
for (auto &[y, w] : ccs[x]) {
acc += w;
w = acc;
}
}
auto fget = [&](ll x, ll y) -> ll { // pier at column x up until y
if (x < 0 || n <= x) return 0;
return (upper_bound(ccs[x].begin(), ccs[x].end(), ii{ y, INF })-1)->second;
};
if (n == 2) return max(fget(0, 2), fget(1, 2));
ll ans = fget(1, n); // all second column
for (ll y = 0; y <= n; y++) {
ans = max(ans, fget(0, y) + fget(1, n) - fget(1, y));
}
return ans;
}
