#include "fish.h"
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
class SegTree {
public:
vector<ll> tree;
int n;
SegTree(int _n) : n(_n), tree(4 * _n, -INF) {}
void update(int idx, ll val) {
update(1, 0, n - 1, idx, val);
}
ll query(int left, int right) {
if (left > right) return -INF;
return query(1, 0, n - 1, left, right);
}
private:
void update(int node, int s, int e, int idx, ll val) {
if (s == e) {
tree[node] = val;
return;
}
int m = (s + e) / 2;
if (idx <= m) update(2 * node, s, m, idx, val);
else update(2 * node + 1, m + 1, e, idx, val);
tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
ll query(int node, int s, int e, int left, int right) {
if (right < s || e < left) return -INF;
if (left <= s && e <= right) return tree[node];
int m = (s + e) / 2;
return max(query(2 * node, s, m, left, right), query(2 * node + 1, m + 1, e, left, right));
}
};
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<pair<int, ll>>> fish(N);
for (int i = 0; i < M; i++) {
fish[X[i]].push_back({Y[i], W[i]});
}
vector<vector<int>> possible(N);
for (int i = 0; i < M; i++) {
int col = X[i];
int thresh = Y[i] + 1;
possible[col].push_back(thresh);
if (col - 1 >= 0) possible[col - 1].push_back(thresh);
if (col + 1 < N) possible[col + 1].push_back(thresh);
}
for (int c = 0; c < N; c++) {
possible[c].push_back(0);
sort(possible[c].begin(), possible[c].end());
auto it = unique(possible[c].begin(), possible[c].end());
possible[c].resize(it - possible[c].begin());
}
vector<int> global_y(M + N + 2);
vector<ll> global_sum(M + N + 2);
vector<int> inn(N);
vector<int> outt(N);
int cnt = 0;
for (int c = 0; c < N; c++) {
auto &p = fish[c];
p.push_back({N, 0});
sort(p.begin(), p.end());
int sz = p.size();
++cnt;
global_y[cnt] = p[0].first + 1;
global_sum[cnt] = p[0].second;
inn[c] = cnt;
for (int j = 1; j < sz; j++) {
++cnt;
global_y[cnt] = p[j].first + 1;
global_sum[cnt] = global_sum[cnt - 1] + p[j].second;
}
outt[c] = cnt;
}
auto get_sum_le = [&](int col, int val) -> ll {
if (val < 0) return 0;
if (col < 0 || col >= N) return 0;
int l = inn[col], r = outt[col];
auto it = upper_bound(global_y.begin() + l, global_y.begin() + r + 1, val + 1);
int k = it - global_y.begin() - 1;
if (k < l) return 0;
return global_sum[k];
};
auto get_sum_range = [&](int col, int low, int high) -> ll {
if (low > high) return 0;
return get_sum_le(col, high) - get_sum_le(col, low - 1);
};
vector<vector<ll>> dp_inc(N + 1);
vector<vector<ll>> dp_dec(N + 1);
vector<map<int, ll>> closed_map(N + 1);
closed_map[0][0] = 0;
for (int i = 0; i < N; i++) {
vector<int> Hcur = possible[i];
int s = Hcur.size();
vector<ll> new_inc(s, -INF);
vector<ll> new_dec(s, -INF);
map<int, ll> new_closed;
vector<int> Hprev = (i == 0 ? vector<int>{0} : possible[i - 1]);
vector<ll> prev_inc = (i == 0 ? vector<ll>{0} : dp_inc[i]);
vector<ll> prev_dec = (i == 0 ? vector<ll>{-INF} : dp_dec[i]);
int t = Hprev.size();
int j0 = lower_bound(Hcur.begin(), Hcur.end(), 0) - Hcur.begin();
if (j0 == s || Hcur[j0] != 0) j0 = -1;
// from prev_inc
{
SegTree st(t);
for (int j = 0; j < t; j++) {
ll val = prev_inc[j] + get_sum_le(i, Hprev[j] - 1) - get_sum_le(i - 1, Hprev[j] - 1);
st.update(j, val);
}
for (int k = 0; k < s; k++) {
ll h = Hcur[k];
ll const_k = -get_sum_le(i, h - 1) + get_sum_le(i - 1, h - 1);
int pos = upper_bound(Hprev.begin(), Hprev.end(), h) - Hprev.begin() - 1;
ll mx = st.query(0, pos);
if (mx > -INF) new_inc[k] = max(new_inc[k], mx + const_k);
int pos2 = lower_bound(Hprev.begin(), Hprev.end(), h) - Hprev.begin();
mx = st.query(pos2, t - 1);
if (mx > -INF) new_dec[k] = max(new_dec[k], mx + const_k);
}
}
// from prev_dec
{
SegTree st(t);
for (int j = 0; j < t; j++) {
ll val = prev_dec[j] + get_sum_le(i, Hprev[j] - 1);
st.update(j, val);
}
for (int k = 0; k < s; k++) {
ll h = Hcur[k];
ll const_k = -get_sum_le(i, h - 1);
// skip for new_inc
int pos2 = lower_bound(Hprev.begin(), Hprev.end(), h) - Hprev.begin();
ll mx = st.query(pos2, t - 1);
if (mx > -INF) new_dec[k] = max(new_dec[k], mx + const_k);
}
}
// from closed_map[i] to new_inc and new_closed
ll val0 = closed_map[i][0];
if (val0 > -INF) {
for (int k = 0; k < s; k++) {
ll h = Hcur[k];
if (h == 0) continue;
ll rsum = get_sum_range(i - 1, 0, h - 1);
ll lsum = get_sum_range(i, h, 0 - 1);
new_inc[k] = max(new_inc[k], val0 + rsum + lsum);
}
}
ll maxv = -INF;
for (auto &p : closed_map[i]) {
maxv = max(maxv, p.second);
}
if (j0 >= 0 && maxv > -INF) {
ll value = maxv + get_sum_range(i, 0, 0 - 1) + 0;
new_closed[0] = max(new_closed[0], value);
}
// update new_closed from prev_inc and prev_dec
if (j0 >= 0) {
for (int j = 0; j < t; j++) {
if (prev_inc[j] == -INF) continue;
ll value = prev_inc[j] + get_sum_range(i, 0, Hprev[j] - 1) + 0;
int h_before = Hprev[j];
new_closed[h_before] = max(new_closed[h_before], value);
}
for (int j = 0; j < t; j++) {
if (prev_dec[j] == -INF) continue;
ll value = prev_dec[j] + get_sum_range(i, 0, Hprev[j] - 1) + 0;
int h_before = Hprev[j];
new_closed[h_before] = max(new_closed[h_before], value);
}
}
dp_inc[i + 1] = new_inc;
dp_dec[i + 1] = new_dec;
closed_map[i + 1] = new_closed;
}
ll ans = 0;
for (auto v : dp_inc[N]) ans = max(ans, v);
for (auto v : dp_dec[N]) ans = max(ans, v);
for (auto &p : closed_map[N]) ans = max(ans, p.second);
return ans;
}
