//#include "fish.h"
#include <bits/stdc++.h>
#define m 1000000
#define ll long long
using namespace std;
vector<pair<ll, ll>> best(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
steg.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> erg;
ll ind = 0, sum = 0;
for (ll i = 0; i < fish.size(); i++)
{
while (steg[ind + 1].first < fish[i].first)
ind++;
erg.push_back({fish[i].first, steg[ind].second + sum});
sum += fish[i].second;
}
return erg;
}
vector<pair<ll, ll>> collect(vector<pair<ll, ll>> scores, vector<pair<ll, ll>> fish) {
// << "collect" << endl;
//(scores);
// << endl;
//(fish);
// << endl;
scores.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> next;
ll ind = 0;
for (ll j = 0; j < fish.size(); j++)
{
while(scores[ind + 1].first < fish[j].first)
ind++;
next.push_back({fish[j].first - 1, scores[ind].second});
}
// << " -> " << endl;
//(next);
// << endl;
return next;
}
vector<pair<ll, ll>> dp(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
// << "dp" << endl;
//(steg);
// << endl;
//(fish);
steg.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> scores;
ll score = 0, score_steg = 0;
ll ind = 0, ind_steg = 0;
ll h;
while (ind + ind_steg < fish.size() + steg.size() - 2) {
if (fish[ind].first < steg[ind_steg].first) {
score += fish[ind].second;
h = fish[ind++].first;
} else {
score_steg = steg[ind_steg].second;
h = steg[ind_steg++].first;
}
if (score_steg > score)
score = score_steg;
scores.push_back({h, score});
}
// << " -> " << endl;
//(scores);
// << endl;
return scores;
}
vector<pair<ll, ll>> inversion(vector<pair<ll, ll>> in, ll n) {
vector<pair<ll, ll>> out;
for (ll i = in.size() - 1; i >= 0; i--)
{
out.push_back({n - in[i].first, in[i].second});
}
return out;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<pair<ll, ll>>> vert(N);
for (ll i = 0; i < M; i++)
{
vert[X[i]].push_back({Y[i], W[i]});
}
for (ll i = 0; i < N; i++)
{
vert[i].push_back({0, 0});
sort(vert[i].begin(), vert[i].end());
}
vector<pair<ll, ll>> up, down;
for (auto a: vert[0]) {
up.push_back({a.first - 1, 0});
down.push_back({a.first - 1, 0});
}
for (ll i = 0; i < N - 1; i++)
{
// << "up" << endl;
//(up);
// << endl;
// << "down" << endl;
//(down);
// << endl << endl;
// << i << " -> " << (i + 1) << endl;
vector<pair<ll, ll>> next_up = collect(dp(up, vert[i]), vert[i + 1]);
vector<pair<ll, ll>> next_down = collect(inversion(dp(inversion(down, N), inversion(vert[i + 1], N)), N), vert[i + 1]);
// << "up" << endl;
//(next_up);
// << endl;
// << "down" << endl;
//(next_down);
// << endl << endl << endl;
for (ll j = 0; j < next_down.size(); j++)
{
next_down[j].second = max(next_down[j].second, next_up[j].second);
}
if (i != 0) {
vector<pair<ll, ll>> best_zero = best(down, vert[i + 1]);
for (ll j = 0; j < best_zero.size(); j++)
{
next_up[j].second = max(next_up[j].second, best_zero[j].second);
}}
up = next_up;
down = next_down;
assert(up.size() == down.size());
for (int i = 0; i < up.size(); i++)
{
assert(up[i].first == down[i].first);
}
}
return max(down.front().second, up.back().second);
}
