#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 3000;
constexpr i64 inf = 1E18;
void chmax(i64 &a, i64 b) {
if (a < b) {
a = b;
}
}
long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<vector<pair<int, int>>> a(n);
vector<map<int, int>> f(n);
for (int i = 0; i < m; i++) {
f[X[i]][Y[i]] += W[i];
if (X[i] > 0) {
f[X[i] - 1][Y[i]] += 0;
}
if (X[i] < n - 1) {
f[X[i] + 1][Y[i]] += 0;
}
}
for (int i = 0; i < n; i++) {
for (auto [j, x] : f[i]) {
a[i].push_back({j, x});
}
}
vector<vector<i64>> pre(n);
vector<vector<array<i64, 2>>> dp(n);
for (int i = 0; i < n; i++) {
int k = a[i].size();
sort(a[i].begin(), a[i].end());
pre[i].resize(k + 1);
for (int j = 0; j < k; j++) {
pre[i][j + 1] = pre[i][j] + a[i][j].second;
}
dp[i].resize(k + 1, {-inf, -inf});
}
for (int i = 0; i <= int(a[0].size()); i++) {
dp[0][i][0] = dp[0][i][1] = 0;
}
for (int i = 1; i < n; i++) {
i64 best = -inf;
int sz = a[i].size();
int j = 0;
for (int k = 0; k <= sz; k++) {
while (j < int(dp[i - 1].size()) && ((j == 0 ? -1 : a[i - 1][j - 1].first) <= (k == 0 ? -1 : a[i][k - 1].first))) {
chmax(best, dp[i - 1][j][0] - pre[i - 1][j]);
j++;
}
// chmax(best, dp[i - 1][k][0] - pre[i - 1][k]);
// if (i == 2) {
// cout << best << " " << pre[i - 1][k] << " h\n";
// }
if (k == 0) {
chmax(dp[i][k][0], best);
} else {
int p = upper_bound(a[i - 1].begin(), a[i - 1].end(), pair<int, int>{a[i][k - 1].first, 2E9}) - a[i - 1].begin();
chmax(dp[i][k][0], best + pre[i - 1][p]);
}
}
best = -inf;
j = a[i - 1].size();
for (int k = sz; k >= 0; k--) {
while (j >= 0 && ((j == 0 ? -1 : a[i - 1][j - 1].first) >= (k == 0 ? -1 : a[i][k - 1].first))) {
if (j == 0) {
chmax(best, dp[i - 1][j][1]);
} else {
int p = upper_bound(a[i].begin(), a[i].end(), pair<int, int>{a[i - 1][j - 1].first, 2E9}) - a[i].begin();
chmax(best, dp[i - 1][j][1] + pre[i][p]);
}
j--;
}
// if (i == 3)
// cerr << "a " << k << " " << best << "\n";
// chmax(best, dp[i - 1][k][1] + pre[i][k]);
if (k == 0) {
chmax(dp[i][k][1], best);
} else {
chmax(dp[i][k][1], best - pre[i][k]);
}
}
// cerr << "F\n";
if (i >= 2) {
best = -inf;
j = a[i - 2].size();
for (int k = sz; k >= 0; k--) {
while (j >= 0 && ((j == 0 ? -1 : a[i - 2][j - 1].first) >= (k == 0 ? -1 : a[i][k - 1].first))) {
if (j == 0) {
chmax(best, dp[i - 2][j][1]);
} else {
int p = upper_bound(a[i - 1].begin(), a[i - 1].end(), pair<int, int>{a[i - 2][j - 1].first, 2E9}) - a[i - 1].begin();
chmax(best, dp[i - 2][j][1] + pre[i - 1][p]);
}
j--;
}
// chmax(best, dp[i - 2][k][1] + pre[i - 1][k]);
chmax(dp[i][k][0], best);
}
best = -inf;
j = 0;
for (int k = 0; k <= sz; k++) {
while (j < int(dp[i - 2].size()) && ((j == 0 ? -1 : a[i - 2][j - 1].first) <= (k == 0 ? -1 : a[i][k - 1].first))) {
chmax(best, dp[i - 2][j][1]);
j++;
}
// chmax(best, dp[i - 2][k][1]);
if (k == 0) {
chmax(dp[i][k][0], best);
} else {
int p = upper_bound(a[i - 1].begin(), a[i - 1].end(), pair<int, int>{a[i][k - 1].first, 2E9}) - a[i - 1].begin();
chmax(dp[i][k][0], best + pre[i - 1][p]);
}
}
}
// cerr << "D\n";
for (int j = 0; j <= sz; j++) {
chmax(dp[i][j][1], dp[i][j][0]);
}
if (i + 1 < n)
chmax(dp[i + 1][0][0], dp[i][0][1]);
}
// cout << dp[3][0][1] << "\n";
// cout << dp[3][1][1] << "\n";
i64 ans = 0;
for (int i = 0; i <= int(a[n - 1].size()); i++) {
ans = max(ans, dp[n - 1][i][1]);
}
return ans;
}
