#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
vector<pair<int, int>> fish[N];
vector<int> use[N];
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
for (int i = 0; i < m; i++) {
fish[x[i]].emplace_back(y[i], w[i]);
if (x[i]) use[x[i]-1].push_back(y[i]);
if (x[i] < n-1) use[x[i]+1].push_back(y[i]);
}
for (int i = 0; i < n; i++) {
use[i].push_back(-1);
sort(use[i].begin(), use[i].end());
sort(fish[i].begin(), fish[i].end());
}
vector<ll> prv_l{0}, prv_r{0};
vector<int> prv_h{-1};
vector<pair<int, int>> prv_fish;
for (int c = 0; c < n; c++) {
int k = sz(use[c]);
vector<ll> cur_l(k), cur_r(k);
auto cur_h = use[c];
auto cur_fish = fish[c];
vector<ll> ps_prv(sz(prv_fish));
vector<ll> ps_cur(sz(cur_fish));
for (int i = 0; i < sz(prv_fish); i++) {
ps_prv[i] = prv_fish[i].second;
if (i) ps_prv[i] += ps_prv[i-1];
}
for (int i = 0; i < sz(cur_fish); i++) {
ps_cur[i] = cur_fish[i].second;
if (i) ps_cur[i] += ps_cur[i-1];
}
vector<ll> my_ps_prv(sz(cur_h));
vector<ll> his_ps_prv(sz(prv_h));
for (int j = 0; j < sz(cur_h); j++) {
my_ps_prv[j] = upper_bound(prv_fish.begin(), prv_fish.end(), pair<int, int>{cur_h[j], MOD}) - prv_fish.begin() - 1;
if (my_ps_prv[j] < 0) my_ps_prv[j] = 0;
else my_ps_prv[j] = ps_prv[my_ps_prv[j]];
}
for (int i = 0; i < sz(prv_h); i++) {
his_ps_prv[i] = upper_bound(prv_fish.begin(), prv_fish.end(), pair<int, int>{prv_h[i], MOD}) - prv_fish.begin() - 1;
if (his_ps_prv[i] < 0) his_ps_prv[i] = 0;
else his_ps_prv[i] = ps_prv[his_ps_prv[i]];
}
vector<ll> my_ps_cur(sz(cur_h));
vector<ll> his_ps_cur(sz(prv_h));
for (int j = 0; j < sz(cur_h); j++) {
my_ps_cur[j] = upper_bound(cur_fish.begin(), cur_fish.end(), pair<int, int>{cur_h[j], MOD}) - cur_fish.begin() - 1;
if (my_ps_cur[j] < 0) my_ps_cur[j] = 0;
else my_ps_cur[j] = ps_cur[my_ps_cur[j]];
}
for (int i = 0; i < sz(prv_h); i++) {
his_ps_cur[i] = upper_bound(cur_fish.begin(), cur_fish.end(), pair<int, int>{prv_h[i], MOD}) - cur_fish.begin() - 1;
if (his_ps_cur[i] < 0) his_ps_cur[i] = 0;
else his_ps_cur[i] = ps_cur[his_ps_cur[i]];
}
ll mx_prv_l = *max_element(prv_l.begin(), prv_l.end());
ll mx_prv_r = *max_element(prv_r.begin(), prv_r.end());
ll best1 = -INF;
ll best2 = -INF;
ll best3 = -INF;
ll best4 = -INF;
ll best5 = -INF;
for (int i = 0; i < sz(prv_h); i++) {
best1 = max(best1, prv_r[i] - his_ps_prv[i]);
best2 = max(best2, prv_r[i] - his_ps_prv[i] + his_ps_cur[i]);
best3 = max(best3, prv_r[i] - his_ps_prv[i]);
best4 = max(best4, prv_r[i] + his_ps_cur[i]);
best5 = max(best5, prv_l[i] + his_ps_cur[i]);
}
for (int j = 0; j < sz(cur_h); j++) {
cur_r[j] = max(cur_r[j], mx_prv_l);
cur_r[j] = max(cur_r[j], mx_prv_r);
cur_r[j] = max(cur_r[j], my_ps_prv[j] + best1);
cur_l[j] = max(cur_l[j], best2 + my_ps_prv[j] - my_ps_cur[j]);
cur_l[j] = max(cur_l[j], best3 + my_ps_prv[j]);
cur_l[j] = max(cur_l[j], best4 - my_ps_cur[j]);
cur_l[j] = max(cur_l[j], mx_prv_r);
cur_l[j] = max(cur_l[j], best5 - my_ps_cur[j]);
cur_l[j] = max(cur_l[j], mx_prv_l);
/*
for (int i = 0; i < sz(prv_h); i++) {
ll cost_prv = prv_r[i] + max(my_ps_prv[j] - his_ps_prv[i], 0LL);
cost_prv = max(cost_prv, prv_l[i]);
cost_prv += max(his_ps_cur[i] - my_ps_cur[j], 0LL);
cur_l[j] = max(cur_l[j], cost_prv);
}
*/
}
swap(prv_l, cur_l);
swap(prv_r, cur_r);
swap(prv_h, cur_h);
swap(prv_fish, cur_fish);
}
ll ans = 0;
for (ll x : prv_l) ans = max(ans, x);
for (ll x : prv_r) ans = max(ans, x);
return ans;
}
