#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using num = long long;
using idata = vector<int>;
using igrid = vector<idata>;
using ndata = vector<num>;
using ngrid = vector<ndata>;
using nmap = map<int, num>;
const num INF = 1e18;
const num NINF = -INF;
template <typename U, typename V>
struct MapCumul {
map<U, V> s;
V d;
MapCumul (map<U, V> &m, V start) {
V h = start;
d = start;
for (const auto &X : m) {
h += X.second;
s.insert({ X.first, h });
}
}
V get (U x) {
auto it = s.upper_bound(x);
if (it == s.begin()) return d;
it --;
return (*it).second;
}
};
struct LocalResult {
int N;
map<int, num> ascend, descend;
// ascend[0] = descend[0]
// ascend[i] => ascend[j] ifof i < j
// descend[i] => descend[j] ifof i > j
LocalResult (int _N) {
N = _N;
ascend.insert({ 0, 0 });
}
LocalResult next (nmap &weights) {
LocalResult next(N);
MapCumul<int, num> cumul(weights, 0);
vector<int> positions = { 0 };
for (const auto &data : weights) {
if (positions[positions.size()] + 1 != data.first)
positions.push_back(data.first - 1);
positions.push_back(data.first);
}
if (positions[positions.size() - 1] != N)
positions.push_back(N);
auto it_ascend = ascend.begin();
auto it_descend = descend.begin();
num opt_ascend = NINF;
num opt_desc_c = NINF;
num opt_desc = NINF;
for (const auto &descend_data : descend) {
opt_desc_c = max(
opt_desc_c,
descend_data.second + cumul.get(descend_data.first)
);
}
for (int i = 1; i <= positions.size(); i ++) {
num mx = NINF;
int pos = positions[i];
num cml = cumul.get(pos);
while (it_ascend != ascend.end() && (*it_ascend).first <= pos) {
int pas = (*it_ascend).first;
num vas = (*it_ascend).second;
opt_ascend = max(opt_ascend, vas - cumul.get(pas));
it_ascend ++;
}
mx = max(mx, opt_ascend + cml);
while (it_descend != descend.end() && (*it_descend).first <= pos) {
int pds = (*it_descend).first;
num vds = (*it_descend).second;
opt_desc = max(opt_desc, vds);
it_descend ++;
}
mx = max(mx, opt_desc + cumul.get(pos));
mx = max(mx, opt_desc_c);
next.ascend.insert({ pos, mx });
}
it_descend = descend.end();
if (it_descend != descend.begin()) it_descend --;
bool cdescend = it_descend != descend.end();
num opt_descpc = NINF;
for (int i = positions.size() - 1; i >= 0; i --) {
int pos = positions[i];
num cml = cumul.get(pos);
num mx = NINF;
while (cdescend && (*it_descend).first >= pos) {
int pas = (*it_descend).first;
num pbs = (*it_descend).second;
opt_descpc = max(
opt_descpc,
pbs + cumul.get(pas)
);
if (it_descend == descend.begin()) cdescend = false;
else it_descend --;
}
mx = max(mx, opt_descpc - cml);
next.descend.insert({ pos, mx });
}
for (const auto &ascend_data : ascend) {
int pos = ascend_data.first;
auto it = next.descend.find(pos);
num res = ascend_data.second;
if (it != next.descend.end()) {
const auto f = *it;
res = max(res, f.second);
next.descend.erase(pos);
}
next.descend.insert({ pos, res });
}
return next;
}
};
ndata cumul (ndata &arr) {
ndata res (arr.size() + 1, 0);
for (int i = 0; i < arr.size(); i ++)
res[i + 1] = res[i] + arr[i];
return res;
}
num max_weights(int N, int M, idata X, idata Y, idata W) {
LocalResult result (N);
vector<map<int, num>> grid(N + 1);
for (int i = 0; i < M; i ++)
grid[X[i] + 1].insert({ Y[i] + 1, W[i] });
num res = NINF;
for (int i = 0; i <= N; i ++) {
result = result.next( grid[i] );
if (i == N - 1) {
for (const auto &u : result.ascend) res = max(res, u.second);
}
}
for (const auto &u : result.descend) res = max(res, u.second);
return res;
}
