#include "fish.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define s second
#define f first
using namespace std;
const int N = 100005;
ll dp[N][5];
vector <ll> p[N],pref[N];
vector <pair<ll,ll> > prc[N],v[N],suff[N];
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
for (int i = 0;i < m; i++){
X[i]++,Y[i]++;
v[X[i] + 1].pb({Y[i],0});
v[X[i] - 1].pb({Y[i],0});
v[X[i]].pb({Y[i],(ll)W[i]});
}
for (int j = 1; j <= n; j++){
v[j].pb({0,0LL}),v[j].pb({n,0LL});
sort(v[j].begin(),v[j].end());
vector <pair<ll,ll>> vec; vec.clear();
vec.pb(v[j][0]);
for (int i = 1; i < v[j].size(); i++){
if (v[j][i].f == vec.back().f) vec[vec.size() - 1].s += v[j][i].s;
else vec.pb(v[j][i]);
}
v[j] = vec;
p[j].pb(v[j][0].s);
for (int i = 1; i < v[j].size(); i++)
p[j].pb(v[j][i].s + p[j][i - 1]);
}
for (int j = 1; j <= n; j++){
for (int i = 0; i < v[j].size(); i++){
ll a = v[j][i].f,val2 =0,val=0,valp = 0,vals=0;
int l,r;
if (j > 1){
l = 0,r = v[j - 1].size() - 1;
while (l <= r){
int mid = (l+r)>>1;
if (v[j - 1][mid].f <= a) {
valp = pref[j - 1][mid];
val2 = p[j - 1][mid];
l = mid + 1;
}
else r = mid - 1;
}
}
l=0,r=suff[j-1].size()-1,vals=0;
while (l<=r){
int mid= (l+r)>>1;
if (suff[j - 1][mid].f >= a) {
vals = suff[j - 1][mid].s;
l = mid + 1;
} else r = mid - 1;
}
dp[a][0] = vals - p[j][i];
dp[a][1] = valp + val2;
if (j < 3) continue;
l = 0,r = prc[j - 2].size() - 1,val = 0;
while (l<=r){
int mid= (l+r)>>1;
if (prc[j - 2][mid].f <= a)
val = prc[j - 2][mid].s,l=mid+1;
else r = mid-1;
}
dp[a][1] = max(dp[a][1], val + val2);
}
if (j == n) break;
ll ls = 0;
for (int i=v[j].size() - 1;i >= 0; i--){
ll a = v[j][i].f,val=0;
int l =0,r = v[j + 1].size() - 1;
while (l<=r){
int mid=(l+r)>>1;
if (v[j + 1][mid].f <= a){
val = p[j + 1][mid];
l = mid + 1;
}else r = mid - 1;
}
suff[j].pb({a,max(ls, max(dp[a][0],dp[a][1]) + val)});
ls = max(ls, max(dp[a][0],dp[a][1]) + val);
}
ls = 0;
for (int i=0;i<v[j].size();i++){
ll a = v[j][i].f;
pref[j].pb(max(ls,dp[a][1] - p[j][i]));
ls= max(ls,dp[a][1] - p[j][i]);
}
ls=0;
for (int i=0;i<v[j].size();i++){
ll a = v[j][i].f;
prc[j].pb({a,max(ls, max(dp[a][0],dp[a][1]))});
ls = prc[j][i].s;
}
}
ll ans = 0;
for (int i=0;i<v[n].size();i++){
int a = v[n][i].f;
ans=max({ans,dp[a][0],dp[a][1]});
}
return ans;
}
