#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef long long ll;
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<vector<int>> p(n + 3);
for (int i = 0; i < m; i++)
for (int d = x[i] == 0 ? 0 : -1; d < (x[i] == n - 1 ? 1 : 2); d++)
p[x[i] + d + 1].push_back(y[i]);
vector<vector<ll>> ws(n + 3);
for (int i = 0; i < n + 3; i++) {
p[i].push_back(-1);
sort(p[i].begin(), p[i].end());
p[i].erase(unique(p[i].begin(), p[i].end()), p[i].end());
ws[i].resize(sz(p[i]));
}
for (int i = 0; i < m; i++) {
int j = (int) (lower_bound(p[x[i] + 1].begin(), p[x[i] + 1].end(), y[i]) - p[x[i] + 1].begin());
ws[x[i] + 1][j] += w[i];
}
for (int i = 0; i < n + 3; i++)
for (int j = 1; j < sz(ws[i]); j++)
ws[i][j] += ws[i][j - 1];
auto weightBelow = [&](int i, int j) {
int k = (int) (upper_bound(p[i].begin(), p[i].end(), j) - p[i].begin()) - 1;
return ws[i][k];
};
vector<vector<ll>> dpu(n + 3), dpd(n + 3);
dpu[0].push_back(0);
dpd[0].push_back(0);
for (int i = 1; i < n + 2; i++) {
dpu[i].resize(sz(p[i]));
dpd[i].resize(sz(p[i]));
ll mdp = 0;
for (int j = 0, k = 0; j < sz(p[i]); j++) {
while (k < sz(p[i - 1]) && p[i - 1][k] <= p[i][j])
mdp = max(mdp, dpu[i - 1][k] - weightBelow(i - 1, p[i - 1][k])), k++;
dpu[i][j] = mdp + weightBelow(i - 1, p[i][j]);
}
mdp = 0;
for (int j = sz(p[i]) - 1, k = sz(p[i - 1]) - 1; j >= 0; j--) {
while (k >= 0 && p[i - 1][k] >= p[i][j])
mdp = max(mdp, dpd[i - 1][k]), k--;
dpd[i][j] = max(dpd[i][j], mdp - weightBelow(i, p[i][j]) + weightBelow(i + 1, p[i][j]));
}
if (i > 1) {
mdp = 0;
for (int j = 0, k = 0; j < sz(p[i]); j++) {
while (k < sz(p[i - 2]) && p[i - 2][k] <= p[i][j])
mdp = max(mdp, dpd[i - 2][k] - weightBelow(i - 1, p[i - 2][k])), k++;
dpu[i][j] = max(dpu[i][j], mdp + weightBelow(i - 1, p[i][j]));
}
mdp = 0;
for (int j = sz(p[i]) - 1, k = sz(p[i - 2]) - 1; j >= 0; j--) {
while (k >= 0 && p[i - 2][k] >= p[i][j])
mdp = max(mdp, dpd[i - 2][k]), k--;
dpu[i][j] = max(dpu[i][j], mdp);
}
}
for (int j = 0; j < sz(p[i]); j++)
dpd[i][j] = max(dpd[i][j], dpu[i][j] + weightBelow(i + 1, p[i][j]));
}
return dpd[n + 1][0];
}
