#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
const int mxn = 3005;
ll grid[mxn][mxn], pfx[mxn][mxn], dp[mxn][mxn];
ll pfxgap0[mxn][mxn], sfxgap0[mxn][mxn];
ll pfxgap1[mxn][mxn], sfxgap1[mxn][mxn];
ll gap2[mxn];
ll r(int x, int y) {
if (x != N - 1) return pfx[x + 1][y];
return (ll)0;
}
ll l(int x, int y) {
if (x) return pfx[x - 1][y];
return (ll)0;
}
ll m(int x, int y) { return pfx[x][y]; }
ll max_weights(int n, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
N = n;
for (int i = 0; i < M; i++) grid[X[i]][++Y[i]] = W[i];
for (int x = 0; x < N; x++) {
pfx[x][0] = grid[x][0];
for (int y = 1; y <= N; y++) pfx[x][y] = pfx[x][y - 1] + grid[x][y];
}
for (int y = 0; y <= N; y++) dp[0][y] = r(0, y);
for (int y = 0; y <= N; y++) dp[1][y] = l(0, y);
for (int x = 2; x < N; x++) {
for (int y = 0; y <= N; y++) {
// 0 gap
dp[x][y] = max(dp[x][y], pfxgap0[x - 1][y] + l(x, y) + r(x, y));
dp[x][y] = max(dp[x][y], sfxgap0[x - 1][y] + r(x, y) - m(x, y));
// 1 gap
dp[x][y] = max(dp[x][y], sfxgap1[x - 2][y] + r(x, y));
dp[x][y] = max(dp[x][y], pfxgap1[x - 2][y] + l(x, y) + r(x, y));
// 2 gap
if (x >= 3) {
dp[x][y] = max(dp[x][y], gap2[x - 3]);
}
}
for (int y = 0; y <= N; y++) {
// prefix gap 0
ll g0 = dp[x][y] - r(x, y) - m(x, y);
pfxgap0[x][y] = max((y ? pfxgap0[x][y - 1] : (ll)0), g0);
// prefix gap 1
ll g1 = dp[x][y] - r(x, y);
pfxgap1[x][y] = max((y ? pfxgap1[x][y - 1] : (ll)0), g1);
// gap 2
gap2[x] = max(gap2[x], dp[x][y]);
}
for (int y = N; y >= 0; y--) {
// suffix gap 0
ll g0 = dp[x][y];
sfxgap0[x][y] = max((y != N ? sfxgap0[x][y + 1] : (ll)0), g0);
// suffix gap 1
ll g1 = dp[x][y];
sfxgap1[x][y] = max((y != N ? sfxgap1[x][y + 1] : (ll)0), g1);
}
}
ll ans = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) ans = max(ans, dp[i][j]);
return ans;
}
