#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll INF = (ll)1e18;
#define mem(a , b) memset(a, b ,sizeof(a))
const ll N = 1e5 + 5;
ll dp[2][2][2][N], pref[2][2][2][N], suf[2][2][2][N];
ll n;
vector < ii > v[N];
vector < ll > sum[N];
long long max_weights(int _n, int m, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
n = _n;
mem(dp, 0); mem(pref, 0);
for(ll i = 0; i < m; i++){
v[X[i]].pb({Y[i], 0});
v[X[i]].pb({Y[i] + 1, W[i]});
}
for(ll i = 0; i < n; i++){
v[i].pb({n, 0}); v[i].pb({0, 0});
sort(v[i].begin(), v[i].end());
vector < ii > f;
for(ll j = 0; j < v[i].size(); j++){
if(!f.size()){
f.pb(v[i][j]);
}else{
if(f.back().ff == v[i][j].ff){
f.pop_back();
}
f.pb(v[i][j]);
}
}
v[i] = f;
ll S = 0;
for(ll j = 0; j < v[i].size(); j++){
S += v[i][j].ss; sum[i].pb(S);
}
}
auto get = [&](ll i, ll k){
auto it = upper_bound(v[i].begin(), v[i].end(), make_pair(k+1, -INF)) - v[i].begin() - 1;
if(it < 0) it = 0;
return sum[i][it];
};
ll row = 0;
ll ans = 0;
for(ll i = 0; i < n; i++){
row ^= 1;
// 0 -> i-1 > i, i > i+1
// 1 -> i-1 < i, i < i+1
// 0 -> sz[i-1] < sz[i], sz[i] < sz[i+1]
// 1 -> sz[i-1] > sz[i], sz[i] > sz[i+1]
ll sz = v[i].size();
for(ll j = 0; j <= sz; j++){
for(ll c = 0; c < 2; c++)
dp[row][c][0][j] = dp[row][c][1][j] = -INF;
}
for(ll l = 0; l < 2; l++){
for(ll d1 = 0; d1 < 2; d1++){
for(ll r = 0; r < 2; r++){
for(ll d2 = 0; d2 < 2; d2++){
if((!l && d1) && (r && !d2)) continue;
for(ll j = 0; j < sz; j++){
ll V = 0;
ll J = 0;
if(i > 0){
auto it = upper_bound(v[i-1].begin(), v[i-1].end(), make_pair(v[i][j].ff, -INF)) - v[i-1].begin();
if(it == v[i-1].size()) it--;
J = it;
}
if(l == 0 && d1){
V = suf[1-row][l][d1][J] - get(i, v[i][j].ff);
}else if(l == 0){
V = pref[1-row][l][d1][J-1];
}
if(l == 1 && !d1){
V = pref[1-row][l][d1][J-1] + (i > 0 ? get(i - 1, v[i][j].ff) : 0);
}else if(l == 1){
V = suf[1-row][l][d1][J];
}
if(r == 0 && d2 && i + 1 < n){
V += get(i + 1, v[i][j].ff);
}
if(r == 1 && !d2){
V -= get(i, v[i][j].ff);
}
dp[row][r][d2][j] = max(dp[row][r][d2][j], V);
ans = max(ans, V);
}
}
}
}
}
// cout << i << ' ' << ans << '\n';
for(ll c = 0; c < 2; c++){
for(ll d = 0; d < 2; d++){
suf[row][c][d][sz] = -INF;
for(ll j = sz; j >= 0; j--){
suf[row][c][d][j] = max(suf[row][c][d][j + 1], dp[row][c][d][j]);
}
for(ll j = 0; j < sz; j++){
pref[row][c][d][j] = max(dp[row][c][d][j], (j > 0 ? pref[row][c][d][j - 1]: -INF));
}
}
}
}
return ans;
}
