#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);
for (int i = 1; i <= positions.size(); i ++) {
num mx = NINF;
int pos = positions[i];
num cml = cumul.get(pos);
for (const auto &ascend_data : ascend) {
if (ascend_data.first > pos) break ;
int pas = ascend_data.first;
num vas = ascend_data.second;
mx = max(mx, vas - cumul.get(pas) + cml);
}
for (const auto &descend_data : descend) {
int qps = max(pos, descend_data.first);
mx = max(mx, descend_data.second + cumul.get(qps));
}
next.ascend.insert({ pos, mx });
}
num opt_d_pc = NINF;
for (int i = positions.size() - 1; i >= 0; i --) {
int pos = positions[i];
num cml = cumul.get(pos);
num mx = NINF;
for (const auto &descend_data : descend) {
if (descend_data.first < pos) continue ;
mx = max(mx, descend_data.second - cml + cumul.get(descend_data.first));
}
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;
}
