#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];
map<int, ll> dp[maxn], dpt[maxn], d[maxn];
map<int, ll> pref[maxn], mx[maxn], suff[maxn];
map<int, 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]++;
a[x[i]][y[i]] += w[i];
for(int d=-1;d<=1;d++){
s[x[i] + d].push_back(y[i]);
}
}
s[0] = {0};
for(int i=1;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());
ll sum = 0;
for(int x:s[i]){
sum += a[i][x];
pref[i][x] = sum;
}
}
for(int i=1;i<=n;i++){
ll val = -1e18;
for(int x:s[i]){
auto it = upper_bound(s[i-1].begin(), s[i-1].end(), x) - s[i-1].begin() - 1;
int y = s[i-1][it];
dp[i][x] = max(mx[i-1][y] + pref[i-1][y], mval[i-1][y]);
d[i][x] = max(dp[i][x], suff[i-1][y] - pref[i][x]);
val = max(val, d[i][x]);
mval[i][x] = val;
ans = max(ans, d[i][x]);
}
for(auto x:s[i-1]){
auto it = upper_bound(s[i].begin(), s[i].end(), x) - s[i].begin() - 1;
int y = s[i][it];
dpt[i][x] = d[i-1][x] + pref[i][y];
}
val = -1e18;
for(int x:s[i]){
auto it = upper_bound(s[i-1].begin(), s[i-1].end(), x) - s[i-1].begin() - 1;
int y = s[i-1][it];
val = max(val, max(dp[i][x], dpt[i][y]) - pref[i][x]);
mx[i][x] = val;
}
val = -1e18;
if(i < n){
for(int j=(int)s[i].size() - 1;j>=0;j--){
int x = s[i][j];
auto it = upper_bound(s[i+1].begin(), s[i+1].end(), x) - s[i+1].begin() - 1;
int y = s[i+1][it];
val = max(val, d[i][x] + pref[i+1][y]);
suff[i][x] = val;
}
}
}
return ans;
}
