#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vi = vector<int>;
using vvi = vector<vi>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())
const int lg = 18;
void selfmax(ll& a, ll b)
{
a = max(a, b);
}
const int maxN = 100'000;
vpll fish[1 + maxN];
vll fishpref[1 + maxN];
int maxind(int i, int h)
{
//return max ind of col i so that corresponding height is <= h
int b = -1;
for(int e = lg; e >= 0; e--)
{
if(b + (1<<e) < sz(fish[i]) && fish[i][b + (1<<e)].first <= h)
b += (1<<e);
}
return b;
}
ll htwt(int i, int h)
{
int j = maxind(i, h);
if(j == -1)
return 0;
else
return fishpref[i][j];
}
ll max_weights(int N, int M, vi X, vi Y, vi W)
{
for(int j = 0; j < M; j++)
{
X[j]++;
Y[j]++;
}
// vpll fish[1+N];
// vll fishpref[1+N];
for(int j = 0; j < M; j++)
{
fish[X[j]].push_back({Y[j], W[j]});
}
for(int r = 1; r <= N; r++)
{
fish[r].push_back({N+1, 0});
sort(fish[r].begin(), fish[r].end());
if(fish[r][0].first != 1)
{
fish[r].insert(fish[r].begin(), {1, 0});
}
fishpref[r] = vll(sz(fish[r]));
for(int i = 0; i < sz(fishpref[r]); i++)
{
fishpref[r][i] = (i == 0 ? 0 : fishpref[r][i-1]) + fish[r][i].second;
}
}
fish[0] = vpll{{0, 0}};
fishpref[0] = vll{0};
vvll inc(1+N), dec(1+N);
vvll incpref(1+N), decpref(1+N); //pref inc dec mx
inc[0] = dec[0] = vll{0};
// cerr << "done\n";
for(int r = 1; r <= N; r++)
{
incpref[r-1] = inc[r-1];
decpref[r-1] = dec[r-1];
for(int i = 1; i < sz(fish[r-1]); i++)
{
incpref[r-1][i] = max(incpref[r-1][i-1], inc[r-1][i]);
decpref[r-1][i] = max(decpref[r-1][i-1], dec[r-1][i]);
}
inc[r] = dec[r] = vll(sz(fish[r]), 0);
vll Csuff;
if(r >= 2)
{
Csuff = vll(sz(fish[r-2]));
for(int j = sz(fish[r-2])-1; j >= 0; j--)
{
Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + htwt(r-1, fish[r-2][j].first - 1);
if(j+1 < sz(fish[r-2]))
selfmax(Csuff[j], Csuff[j+1]);
}
}
for(int i = 0; i < sz(fish[r]); i++)
{
ll basic = 0;
ll Bcatch = 0;
int Bk = -1;
if(r >= 2)
{
//A
selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + htwt(r-1, fish[r][i].first - 1));
int ploci = maxind(r-2, fish[r][i].first);
//B
/*for(int j = 0; j <= ploci; j++)
{
// cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
ll medcatch = 0;
for(int k = 0; k < sz(fish[r-1]); k++)
if(fish[r-1][k].first <= fish[r][i].first - 1)
medcatch += fish[r-1][k].second;
selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + medcatch);
}*/
while(Bk+1 < sz(fish[r-1]) && fish[r-1][Bk+1].first <= fish[r][i].first - 1)
{
Bk++;
Bcatch += fish[r-1][Bk].second;
}
selfmax(basic, Bcatch + max(incpref[r-2][ploci], decpref[r-2][ploci]));
// for(int j = 0; j <= ploci; j++)
// {
// // cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
// // selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + Bcatch);
// selfmax(basic, )
// }
//C
// for(int j = sz(fish[r-2])-1; j > ploci; j--)
// {
// // cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
// ll medcatch = 0;
// for(int k = 0; k < sz(fish[r-1]); k++)
// if(fish[r-1][k].first <= fish[r-2][j].first - 1)
// medcatch += fish[r-1][k].second;
// selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + medcatch);
// }
if(ploci+1 < sz(fish[r-2]))
{
// cerr << ploci << " : " << sz(fish[r-2]) << '\n';
selfmax(basic, Csuff[ploci+1]);
}
}
selfmax(inc[r][i], basic);
selfmax(dec[r][i], basic);
for(int j = 0; j < sz(fish[r-1]); j++)
{
// cerr << "j = " << j << " , " << fish[r-1][j].first-1 << '\n';
ll ext = 0;
if(fish[r-1][j].first - 1 <= fish[r][i].first - 1)
{
// cerr << "case 1\n";
for(int k = j; k < sz(fish[r-1]); k++)
{
if(fish[r-1][k].first <= fish[r][i].first - 1)
ext += fish[r-1][k].second;
}
selfmax(inc[r][i], inc[r-1][j] + ext);
selfmax(dec[r][i], inc[r-1][j] + ext);
}
else
{
// cerr << "case 2\n";
for(int k = i; k < sz(fish[r]); k++)
{
if(fish[r][k].first <= fish[r-1][j].first - 1)
ext += fish[r][k].second;
}
selfmax(dec[r][i], dec[r-1][j] + ext);
}
// cerr << r << ' ' << fish[r][i].first-1 << " : " << inc[r][i] << ' ' << dec[r][i] << '\n';
}
}
}
ll res = 0;
for(vll x : inc)
for(ll y : x)
res = max(res, y);
for(vll x : dec)
for(ll y : x)
res = max(res, y);
return res;
}
