#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 1e5 + 100;
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
vector<ll> fishes[N];
vector<vector<int>> states(n + 1, {0});
for(int i = 0; i < m; ++i){
++y[i];
for(int k = max(0, x[i] - 1); k <= min(n - 1, x[i] + 1); ++k){
states[k].pb(y[i]);
}
}
for(int i = 0; i <= n; ++i){
sort(states[i].begin(), states[i].end());
states[i].erase(unique(states[i].begin(), states[i].end()), states[i].end());
fishes[i].resize(states[i].size());
}
for(int i = 0; i < m; ++i){
int j = x[i];
int Y = lower_bound(states[j].begin(), states[j].end(), y[i]) - states[j].begin();
fishes[j][Y] += w[i];
}
vector<vector<ll>> dp_up(n + 1), dp_down(n + 1);
for(int i = 0; i <= n; ++i){
int sz = states[i].size();
dp_up[i].resize(sz, 0);
dp_down[i].resize(sz, 0);
if(i > 0){
ll best = dp_down[i - 1][0], sum = 0;
for(int j = 0, left = 0; j < sz; ++j){
while(left + 1 < states[i - 1].size() && states[i - 1][left + 1] <= states[i][j]){
++left;
best += fishes[i - 1][left];
best = max(best, dp_down[i - 1][left]);
}
dp_down[i][j] = max(dp_down[i][j], best);
}
best = 0;
sum = accumulate(fishes[i].begin(), fishes[i].end(), 0ll);
for(int j = sz - 1, left = states[i - 1].size(); j >= 0; --j){
while(left > 0 && states[i - 1][left - 1] >= states[i][j]){
--left;
best = max(best, max(dp_up[i - 1][left], dp_down[i - 1][left]) + sum);
}
dp_up[i][j] = max(dp_up[i][j], best - sum);
sum -= fishes[i][j];
}
}
if(i > 1){
ll best = max(dp_down[i - 2][0], dp_up[i - 2][0]), sum = 0;
for(int j = 0, left = 0, leftt = 0; j < sz; ++j){
while(leftt + 1 < states[i - 2].size() && states[i - 2][leftt + 1] <= states[i][j]){
++leftt;
while(left + 1 < states[i - 1].size() && states[i - 1][left + 1] <= states[i][j]){
++left;
sum += fishes[i - 1][left];
best += fishes[i - 1][left];
}
best = max(best, max(dp_down[i - 2][leftt], dp_up[i - 2][leftt]) + sum);
}
dp_down[i][j] = max(dp_down[i][j], best);
}
best = 0;
sum = accumulate(fishes[i - 1].begin(), fishes[i - 1].end(), 0ll);
for(int j = sz - 1, left = states[i - 1].size(), leftt = states[i - 2].size(); j >= 0; --j){
while(leftt - 1 > 0 && states[i - 2][leftt - 1] >= states[i][j]){
--leftt;
while(left - 1 > 0 && states[i - 1][left - 1] >= states[i - 2][leftt]){
--left;
sum -= fishes[i - 1][left];
}
best = max(best, max(dp_down[i - 2][leftt], dp_up[i - 2][leftt]) + sum);
}
dp_down[i][j] = max(dp_down[i][j], best);
}
}
}
return max(dp_up[n][0], dp_down[n][0]);
}
