#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
struct fish {
ll x, y, w;
};
ll max_weights(int N, int M, vi X, vi Y, vi W) {
typedef vector<fish> vf;
typedef vector<vf> vvf;
vf f;
L(i, 0ll, M) {
f.pb({X[i], Y[i], W[i]});
}
sort(f.begin(), f.end(), [](const fish& f1, const fish& f2) {return f1.y < f2.y;});
vvf fax;
vvll dpinc;
vvll dpdec;
// vvll psum;
L(i, 0ll, N) {
vf faxr(1ll, {i, 0ll, 0ll});
vll dpincr(1ll, 0ll);
vll dpdecr(1ll, 0ll);
// vll psumr(N + 1ll, 0ll);
fax.pb(faxr);
dpinc.pb(dpincr);
dpdec.pb(dpdecr);
// psum.pb(psumr);
}
L(i, 0ll, M) {
assert(f[i].x < N);
assert(f[i].y + 1ll <= N);
fax[f[i].x].pb(f[i]);
dpinc[f[i].x].pb(0ll);
dpdec[f[i].x].pb(0ll);
// cout << "Anya likes peanuts, Anya hates carrots" << endl;
// psum[f[i].x][f[i].y + 1ll] += f[i].w; // += because we have multiple fish per cell
}
// Accumulating sums
// L(i, 0ll, N) {
// L(j, 1ll, N + 1ll) {
// psum[i][j] += psum[i][j - 1ll];
// }
// }
// ! CAREFUL: you're adding another value
L(i, 0ll, N) {
fax[i].pb({i, N, 0ll});
dpinc[i].pb(0ll);
dpdec[i].pb(0ll);
}
ll ans = 0ll;
L(i, 1ll, N) {
// Increasing first
const vf& fax1 = fax[i], fax2 = fax[i - 1ll], fax3 = fax[max(i - 2ll, 0ll)];
ll f1s = fax1.size(), f2s = fax2.size(), f3s = fax3.size();
// Case 1: dpinc, normal
ll cur_pref_dpinc_max = dpinc[i - 1ll][0ll], f2i = 0ll;
// ll f2_fish_sum = 0ll, f2fishi = 0ll;
ll f2fishi = 0ll;
// ! THIS LOOP IN PARTICULAR IS SCARY, MIGHT BE WRONG
L(j, 0ll, f1s) {
dpinc[i][j] = max(dpinc[i][j], cur_pref_dpinc_max);
while(f2i < f2s && fax2[f2i].y <= fax1[j].y) {
// Increase f2i: since j has increased, the possible values for f2i has also widened
// First, increase the cur_pref_dpinc_max by the value of the current fish
while(f2fishi < f2s && fax2[f2fishi].y < fax2[f2i].y) {
cur_pref_dpinc_max += (ll)fax2[f2fishi].w;
f2fishi ++;
}
cur_pref_dpinc_max = max(cur_pref_dpinc_max, dpinc[i - 1ll][f2i]); // A new fish is reachable. We need to check if picking just that fish is better
// cout << fax2[f2i].y << " " << fax1[j].y << " " << (j + 1 < f1s ? fax1[j + 1].y : N) << "\n";
// if(fax2[f2i].y == fax1[j].y && fax1[j].y < (j + 1 < f1s ? fax1[j + 1].y : N)) cur_pref_dpinc_max += (ll)fax2[f2i].w;
f2i++;
}
while(f2fishi < f2s && fax2[f2fishi].y < fax1[j].y) {
cur_pref_dpinc_max += (ll)fax2[f2fishi].w;
f2fishi ++;
}
dpinc[i][j] = max(dpinc[i][j], cur_pref_dpinc_max);
}
// ! Developing here
// Case 3: decreasing
ll cur_suff_dpdec_max = max(dpinc[i - 1ll][f2s - 1ll], dpdec[i - 1ll][f2s - 1ll]);
f2i = f2s - 1ll;
LR(j, f1s - 1ll, -1ll) {
cur_suff_dpdec_max += (ll)fax1[j].w; // Increment dpdec max with weight of current fish
while(f2i >= 0 && fax2[f2i].y > fax1[j].y) {
// ! Warning, might be wrong!
// Idea: we only decrease when we get a new fish
// Therefore, we only need to consider the current fish in the dpdec thing (or basta smth like that)
cur_suff_dpdec_max = max(cur_suff_dpdec_max, max(dpinc[i - 1ll][f2i], dpdec[i - 1ll][f2i]) + (ll)fax1[j].w); // A new fish is reachable. We need to check if picking just that fish is better
f2i--;
}
if(f2i >= 0 && fax2[f2i].y == fax1[j].y) { // ! Might be wrong!
cur_suff_dpdec_max = max(cur_suff_dpdec_max, max(dpinc[i - 1ll][f2i], dpdec[i - 1ll][f2i]));
f2i--;
}
dpdec[i][j] = max(dpdec[i][j], cur_suff_dpdec_max);
}
if(i > 1ll) {
// Case 2a: dpinc, transition, second to the last is less
ll max_past_dp = 0ll;
ll cur_dpinc2a_sum = 0ll;
ll f3i = 0ll;
ll f2i = 0ll;
L(j, 0ll, f1s) {
while(f3i < f3s && fax3[f3i].y <= fax1[j].y) {
// compare current max dp with current dp value
max_past_dp = max(max_past_dp, max(dpdec[i - 2ll][f3i], dpinc[i - 2ll][f3i]));
f3i++;
}
while(f2i < f2s && fax2[f2i].y < fax1[j].y) { // ! THIS MIGHT BITE YOU BACK LATER
cur_dpinc2a_sum += (ll)fax2[f2i].w;
f2i++;
}
dpinc[i][j] = max(dpinc[i][j], max_past_dp + cur_dpinc2a_sum);
dpinc[i][j] = max(dpinc[i][j], dpdec[i - 1ll][0ll]); // Case 2b: dpinc, transition, second to the last is greater
}
}
// Update answers
L(j, 0ll, f1s) {
ans = max(ans, dpdec[i][j]);
ans = max(ans, dpinc[i][j]);
}
}
// cout << "Y" << endl;
// L(i, 0ll, N) {
// const vf& fax1 = fax[i];
// ll f1s = fax1.size();
// L(j, 0ll, f1s) {
// cout << fax1[j].y << " ";
// }
// cout << "\n";
// }
// cout << "DPINC" << endl;
// L(i, 0ll, N) {
// const vf& fax1 = fax[i];
// ll f1s = fax1.size();
// L(j, 0ll, f1s) {
// cout << dpinc[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "DPDEC" << endl;
// L(i, 0ll, N) {
// const vf& fax1 = fax[i];
// ll f1s = fax1.size();
// L(j, 0ll, f1s) {
// cout << dpdec[i][j] << " ";
// }
// cout << "\n";
// }
// Final casework for the final answer (do this on the last column)
// ll ans = 0ll;
// const vf& lastcol = fax[N - 1ll];
// ll lastcols = lastcol.size();
// L(i, 0ll, lastcols) {
// ans = max(ans, max(dpdec[N - 1ll][i], dpinc[N - 1ll][i]));
// }
return ans;
}
