#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector <vector<ll>> ps(N+5, vector <ll> (N+5));
for (int i = 0; i < M; i++) {
X[i]++, Y[i]++;
ps[X[i]][Y[i]] += W[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
ps[i][j] += ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1];
}
}
ll dp[N+5][N+5][2], pmx[N+5][N+5][2], smx[N+5][N+5][2];
memset(dp, -0x3f, sizeof(dp));
memset(pmx, -0x3f, sizeof(pmx));
memset(smx, -0x3f, sizeof(smx));
dp[0][0][0] = 0;
ll ans = 0;
auto calc = [&](int i, int j, int x, int y) {
return ps[j][y]-(x == 0 ? 0LL : ps[j][x-1])-(i == 0 ? 0LL : ps[i-1][y])+(i == 0 || x == 0 ? 0LL : ps[i-1][x-1]);
};
for (int i = 0; i <= N; i++) {
if (i) {
for (int j = 0; j <= N; j++) {
dp[i][0][0] = max(dp[i][0][0], dp[i-1][j][0]);
dp[i][0][0] = max(dp[i][0][0], dp[i-1][j][1]);
if (j) {
// increasing
if (i < N) {
dp[i][j][0] = max(dp[i][j][0], pmx[i-1][j-1][0]+ps[i][j]-ps[i-1][j]);
dp[i][j][0] = max(dp[i][j][0], smx[i-1][0][1]+calc(i, i, 1, j));
}
// decreasing
if (i > 1) {
dp[i][j][1] = max(dp[i][j][1], smx[i-1][j+1][0]-(ps[i][j-1]-ps[i-1][j-1]));
dp[i][j][1] = max(dp[i][j][1], dp[i-1][0][0]+calc(i, i, j, N));
}
}
ans = max(ans, dp[i][j][0]);
ans = max(ans, dp[i][j][1]);
}
}
if (i+1 <= N) {
pmx[i][0][0] = pmx[i][0][1] = dp[i][0][0];
for (int j = 1; j <= N; j++) {
pmx[i][j][0] = max(pmx[i][j-1][0], dp[i][j][0]-(ps[i+1][j]-ps[i][j]));
}
for (int j = N; j >= 0; --j) {
smx[i][j][0] = max(smx[i][j+1][0], dp[i][j][1]+(j == 0 ? 0LL : ps[i+1][j-1]-ps[i][j-1]));
smx[i][j][1] = max(smx[i][j+1][1], dp[i][j][1]);
}
}
}
return ans;
}
