#include "fish.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vl> fishes(N+1);
vector<vl> states(N+1, {0});
// initializing states
F(i, 0, M) {
++Y[i];
F(j, max(X[i]-1, 0), min(X[i]+1, N-1) + 1)
states[j].push_back(Y[i]);
}
// rank reduction and correction, i suppose
F(i, 0, N+1) {
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());
}
//
F(i, 0, M) {
int x = X[i];
int y = lower_bound(states[x].begin(), states[x].end(), Y[i]) - states[x].begin();
fishes[x][y] += W[i];
}
vector<vector<long long>> dp_up(N+1), dp_down(N+1);
for (int i = 0; i <= N; ++i) {
int sz = states[i].size();
dp_up[i].assign(sz, 0);
dp_down[i].assign(sz, 0);
if (i > 1) {
long long best = max(dp_up[i-2][0], dp_down[i-2][0]), sum = 0;
for (int j = 0, lef = 0, mid = 0; j < sz; ++j) {
while (lef+1 < (int)states[i-2].size() && states[i-2][lef+1] <= states[i][j]) {
++lef;
while (mid+1 < (int)states[i-1].size() && states[i-1][mid+1] <= states[i-2][lef]) {
++mid;
best += fishes[i-1][mid];
sum += fishes[i-1][mid];
}
best = max(best, max(dp_up[i-2][lef], dp_down[i-2][lef]) + sum);
}
dp_up[i][j] = max(dp_up[i][j], best);
}
best = 0;
sum = accumulate(fishes[i-1].begin(), fishes[i-1].end(), 0LL);
for (int j = sz-1, lef = states[i-2].size(), mid = states[i-1].size(); j >= 0; --j) {
while (lef > 0 && states[i-2][lef-1] >= states[i][j]) {
--lef;
while (mid > 0 && states[i-1][mid-1] > states[i-2][lef]) {
--mid;
sum -= fishes[i-1][mid];
}
best = max(best, max(dp_up[i-2][lef], dp_down[i-2][lef]) + sum);
}
dp_up[i][j] = max(dp_up[i][j], best);
}
}
if (i > 0) {
long long best = dp_up[i-1][0], sum = 0;
for (int j = 0, lef = 0; j < sz; ++j) {
while (lef+1 < (int)states[i-1].size() && states[i-1][lef+1] <= states[i][j]) {
++lef;
best += fishes[i-1][lef];
best = max(best, dp_up[i-1][lef]);
}
dp_up[i][j] = max(dp_up[i][j], best);
}
best = 0;
sum = accumulate(fishes[i].begin(), fishes[i].end(), 0LL);
for (int j = sz-1, lef = states[i-1].size(); j >= 0; --j) {
while (lef > 0 && states[i-1][lef-1] >= states[i][j]) {
--lef;
best = max(best, max(dp_down[i-1][lef], dp_up[i-1][lef]) + sum);
}
dp_down[i][j] = max(dp_down[i][j], best-sum);
sum -= fishes[i][j];
}
}
}
return max(dp_up[N][0], dp_down[N][0]);
}
