#include "fish.h"
#include <bits/stdc++.h>
#define ent '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 12;
vector<int> s[maxn];
vector<ll> dp[maxn], dpt[maxn], d[maxn];
vector<ll> pref[maxn], mx[maxn], suff[maxn];
vector<ll> a[maxn], mval[maxn];
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
ll ans = 0;
for(int i=0;i<m;i++){
x[i]++, y[i]++;
for(int d=-1;d<=1;d++){
s[x[i] + d].push_back(y[i]);
}
}
for(int i=0;i<=n;i++){
s[i].push_back(0);
sort(s[i].begin(), s[i].end());
s[i].resize(unique(s[i].begin(), s[i].end()) - s[i].begin());
dp[i] = d[i] = pref[i] = mx[i] = suff[i] = a[i] = mval[i] = vector<ll> ((int)s[i].size(), 0);
dpt[i] = {0};
}
for(int i=0;i<m;i++){
int j = lower_bound(s[x[i]].begin(), s[x[i]].end(), y[i]) - s[x[i]].begin();
a[x[i]][j] += w[i];
}
for(int i=1;i<=n;i++){
ll sum = 0;
for(int j=0;j<s[i].size();j++){
sum += a[i][j];
pref[i][j] = sum;
}
}
for(int i=1;i<=n;i++){
dpt[i] = vector<ll> (s[i-1].size(), 0);
ll val = -1e18;
for(int j=0;j<(int)s[i].size();j++){
int x = s[i][j];
int it = upper_bound(s[i-1].begin(), s[i-1].end(), x) - s[i-1].begin();
it--;
dp[i][j] = max(mx[i-1][it] + pref[i-1][it], mval[i-1][it]);
d[i][j] = max(dp[i][j], suff[i-1][it] - pref[i][j]);
val = max(val, d[i][j]);
mval[i][j] = val;
ans = max(ans, d[i][j]);
}
for(int j=0;j<(int)s[i-1].size();j++){
int x = s[i-1][j];
int it = upper_bound(s[i].begin(), s[i].end(), x) - s[i].begin();
it--;
dpt[i][j] = d[i-1][j] + pref[i][it];
}
val = -1e18;
for(int j=0;j<(int)s[i].size();j++){
int x = s[i][j];
int it = upper_bound(s[i-1].begin(), s[i-1].end(), x) - s[i-1].begin();
it--;
val = max(val, max(dp[i][j], dpt[i][it]) - pref[i][j]);
mx[i][j] = val;
}
val = -1e18;
if(i < n){
for(int j=(int)s[i].size() - 1;j>=0;j--){
int x = s[i][j];
int it = upper_bound(s[i+1].begin(), s[i+1].end(), x) - s[i+1].begin();
it--;
val = max(val, d[i][j] + pref[i+1][it]);
suff[i][j] = val;
}
}
}
return ans;
}
