#include "fish.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = __LONG_LONG_MAX__/2;
const int NN = 100001;
int max_weights(signed N, signed M, vector<signed> X,vector<signed> Y, vector<signed> W) {
for (int i = 0;i<M;i++) X[i]++,Y[i]++;
vector<vector<pii>> dp(N+2);
vector<vi> prefdp(N+2),sufdp(N+2);
vector<pii> fishes[N+2];
vi pts[N+2];
for (int i=0;i<M;i++) fishes[X[i]].push_back({Y[i],W[i]});
pts[0].push_back(0);
for (int i=1;i<=N+1;i++) {
pts[i].push_back(0);
if (i<N+1) for (auto it :fishes[i-1]) pts[i].push_back(it.ff);
if(i<N+1)for (auto it :fishes[i+1]) pts[i].push_back(it.ff);
if (i < N+1)pts[i].push_back(N);
}
for (int i=1;i<=N+1;i++) {
sort(all(pts[i]));
sort(all(fishes[i]));
pts[i].erase(unique(all(pts[i])),pts[i].end());
}
for (int i=0;i<=N+1;i++) {
dp[i].assign(big(pts[i]),pii{-inf,-inf});
sufdp[i].assign(big(pts[i]),-inf);
prefdp[i].assign(big(pts[i]),-inf);
}
dp[0][0] = {0,0};
vi done(N+2,0);
auto getweights = [&](int col,int h) -> int {
if (fishes[col].empty()) return 0;
if (!done[col]) {
int cur = 0;
for (auto& [hei,wei] : fishes[col]) {
wei+=cur;
cur = wei;
}
done[col] = 1;
}
auto it = upper_bound(all(fishes[col]),pii{h,inf});
if (it == fishes[col].begin()) return 0;
--it;
return it->ss;
};
for (int i=1;i<=N+1;i++) {
--i;
prefdp[i][0] = dp[i][0].ff-getweights(i,pts[i][0]);
for (int j = 1;j<big(pts[i]);j++) {
prefdp[i][j] = max(prefdp[i][j-1],dp[i][j].ff-getweights(i,pts[i][j]));
}
sufdp[i].back() = dp[i].back().ss+getweights(i+1,pts[i].back());
for (int j = big(pts[i])-2;j>=0;j--) {
sufdp[i][j] = max(sufdp[i][j+1],dp[i][j].ss+getweights(i+1,pts[i][j]));
}
++i;
int ptr = -1,ptr2 = big(pts[i-1]);
for (int j=0;j<big(pts[i]);j++) {
int plus = getweights(i-1,pts[i][j]);
while (ptr<big(pts[i-1])-1 && pts[i-1][ptr+1] <= pts[i][j]) ptr++;
while (ptr2 > 0 && pts[i-1][ptr2-1] >= pts[i][j]) ptr2--;
dp[i][j].ff = max(dp[i][j].ff,prefdp[i-1][ptr]+plus);
/* for (int jp = 0;jp<=ptr;jp++) {
dp[i][j].ff = max(dp[i][j].ff,
dp[i-1][jp].ff+plus-getweights(i-1,pts[i-1][jp]));
} */
plus = getweights(i,pts[i][j]);
dp[i][j].ss = max(dp[i][j].ss,sufdp[i-1][ptr2]-plus);
dp[i][j].ss = max(dp[i][j].ss,max(dp[i-1][big(pts[i-1])-1].ff,dp[i-1][big(pts[i-1])-1].ss)-plus+getweights(i,pts[i-1].back()));
/* for (int jp = big(pts[i-1])-1;jp>=ptr2;jp--) {
int mx = dp[i-1][jp].ss;
if (jp == big(pts[i-1])-1) mx = max(mx,dp[i-1][jp].ff);
dp[i][j].ss = max(dp[i][j].ss,
mx-plus+getweights(i,pts[i-1][jp]));
} */
}
//switcheroo!
if (i>2)dp[i].back().ff = max(dp[i].back().ff,dp[i-2].back().ff+getweights(i-1,N));
if (i>=2) dp[i][0].ss = max(dp[i][0].ss,dp[i-2][0].ss);
//swap modes if on edge twice
dp[i][0].ff = max(dp[i][0].ff,max(dp[i-1][0].ff,dp[i-1][0].ss));
dp[i][0].ss = max(dp[i][0].ss,max(dp[i-1][0].ff,dp[i-1][0].ss));
dp[i].back().ss = max(dp[i].back().ss,max(dp[i-1].back().ff,dp[i-1].back().ss));
dp[i].back().ff = max(dp[i].back().ff,max(dp[i-1].back().ff,dp[i-1].back().ss));
}
int ans = 0;
for (pii itt : dp[N+1]) {
ans = max(ans,itt.ff);
ans = max(ans,itt.ss);
}
return ans;
}
