#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][2];
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]+1] = 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 x = 0; x < N; x++) {
// DP
if (x == 0) {
for (int y = 0; y <= N; y++) dp[0][y][0] = dp[0][y][1] = r(0, y);
} else if (x == 1) {
for (int y = 0; y <= N; y++) dp[1][y][0] = dp[1][y][1] = l(1, y);
} else {
for (int y = 0; y <= N; y++) {
// 0 gap
dp[x][y][1] = max(dp[x][y][1], pfxgap0[x - 1][y] + l(x, y) + r(x, y));
dp[x][y][1] = max(dp[x][y][1], sfxgap0[x - 1][y] + r(x, y) - m(x, y));
// 1 gap
dp[x][y][0] = max(dp[x][y][0], sfxgap1[x - 2][y] + r(x, y));
dp[x][y][0] = max(dp[x][y][0], pfxgap1[x - 2][y] + l(x, y) + r(x, y));
dp[x][y][1] = max(dp[x][y][1], sfxgap1[x - 2][y] + r(x, y));
dp[x][y][1] = max(dp[x][y][1], pfxgap1[x - 2][y] + l(x, y) + r(x, y));
// 2 gap
if (x >= 3) {
dp[x][y][0] = max(dp[x][y][0], gap2[x - 3]);
dp[x][y][1] = max(dp[x][y][1], gap2[x - 3]);
}
}
}
// STUFF
for (int y = 0; y <= N; y++) {
// prefix gap 0
ll g0 = dp[x][y][0] - r(x, y) - m(x, y);
pfxgap0[x][y] = max((y ? pfxgap0[x][y - 1] : (ll)0), g0);
// prefix gap 1
ll g1 = max(dp[x][y][0], dp[x][y][1]) - r(x, y);
pfxgap1[x][y] = max((y ? pfxgap1[x][y - 1] : (ll)0), g1);
// gap 2
gap2[x] = max(gap2[x], max(dp[x][y][0], dp[x][y][1]));
}
for (int y = N; y >= 0; y--) {
// suffix gap 0
ll g0 = dp[x][y][0];
sfxgap0[x][y] = max((y != N ? sfxgap0[x][y + 1] : (ll)0), g0);
// suffix gap 1
ll g1 = max(dp[x][y][0], dp[x][y][1]);
sfxgap1[x][y] = max((y != N ? sfxgap1[x][y + 1] : (ll)0), g1);
}
}
// for (int y = 0; y <= N; y++) {
// for (int x = 0; x < N; x++) cout << dp[x][y] << " ";
// cout << '\n';
// }
ll ans = 0; for (int i = 0; i < N; i++) for (int j = 0; j <= N; j++) ans = max(ans, max(dp[i][j][0], dp[i][j][1]));
return ans;
}
