#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<vector<int64_t>> pref(N, vector<int64_t>(N + 1));
vector<vector<int>> a(N, vector<int>(N));
for (int i = 0; i < M; i++) {
a[X[i]][Y[i]] = W[i];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) pref[i][j + 1] = pref[i][j] + a[i][j];
}
const int64_t inf = 1e18;
vector<vector<int64_t>> dp(N + 1, vector<int64_t>(2, -inf));
dp[0][0] = 0;
dp[N][1] = 0;
for (int i = 0; i < N; i++) {
vector<vector<int64_t>> ndp(N + 1, vector<int64_t>(2, -inf));
if (i + 1 < N) {
for (int j = 0; j < N; j++) {
dp[j + 1][0] = max(dp[j + 1][0], dp[j][0] + a[i][j]);
}
}
for (int j = N - 1; j > 0; j--) {
dp[j - 1][1] = max(dp[j - 1][1], dp[j][1] + a[i][j - 1]);
}
if (i == 1) dp[0][0] = max(dp[0][0], pref[0][N]);
if (i + 2 < N) dp[0][0] = max(dp[0][0], dp[0][1]);
if (i == N - 1) break;
for (int j = 0; j <= N; j++) {
ndp[j][0] = max(ndp[j][0], dp[j][0]);
if (j == N) ndp[N][1] = max(ndp[N][1], dp[j][0]);
if (j == 0) ndp[N][1] = max(ndp[N][1], dp[j][0]);
if (j == 0 && i + 1 == N - 1) ndp[N][0] = max(ndp[N][0], dp[0][0] + pref[N - 1][N]);
}
for (int j = 0; j <= N; j++) {
ndp[j][1] = max(ndp[j][1], dp[j][1]);
if (j == N) ndp[N - 1][1] = max(ndp[N - 1][1], dp[j][1] + a[i + 1][N - 1]);
if (i + 2 < N && j == 0) ndp[0][0] = max(ndp[0][0], dp[j][1]);
if (j == 0) ndp[0][0] = max(ndp[0][0], dp[j][1]);
}
ndp.swap(dp);
}
return max(dp[0][1], max(dp[N][0], dp[N][1]));
}
