#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];
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);
inc[0] = dec[0] = vll{0};
// cerr << "done\n";
for(int r = 1; r <= N; r++)
{
inc[r] = dec[r] = vll(sz(fish[r]), 0);
for(int i = 0; i < sz(fish[r]); i++)
{
// cerr << "\n\n";
// cerr << r << " : " << i << " " << fish[r][i].first << '\n';
ll basic = 0;
if(r >= 2) //leave two columns blank.
{
ll thiscatch = 0;
// for(int j = 0; j < sz(fish[r-1]); j++)
// if(fish[r-1][j].first <= fish[r][i].first - 1)
// thiscatch += fish[r-1][j].second;
int b = -1;
for(int e = lg; e >= 0; e--)
{
if(b + (1<<e) < sz(fish[r-1]) && fish[r-1][b + (1<<e)].first <= fish[r][i].first - 1)
b += (1<<e);
}
if(b != -1)
thiscatch += fishpref[r-1][b];
selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + thiscatch);
}
// cerr << "hello\n";
//leave one column blank
if(r >= 2)
{
// for(int j = 0; j < sz(fish[r-2]); 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 <= max(fish[r-2][j].first - 1, fish[r][i].first - 1))
// medcatch += fish[r-1][k].second;
// selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + medcatch);
// }
//case 1: fish[r-2][j].first <= fish[r][i].first
//
//case 2: fish[r-2][j].first >= fish[r][i].first
}
selfmax(inc[r][i], basic);
selfmax(dec[r][i], basic);
// cerr << "oneblank done\n";
// cerr << r << ' ' << fish[r][i].first-1 << " : " << inc[r][i] << ' ' << dec[r][i] << '\n'; }
// cerr << r << ' ' << fish[r][i].first-1 << " : " << inc[r][i] << ' ' << dec[r][i] << '\n';
// cerr << r << ' ' << fish[r][i].first-1 << " : " << inc[r][i] << ' ' << dec[r][i] << '\n';
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;
}
