#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
int K = 0;
vector<vector<int>> A(N, vector(N, 0));
for (int i = 0; i < M; i++) {
A[Y[i]][X[i]] = W[i];
K = max(K, Y[i]);
}
K++;
vector<vector<int>> P(K + 1, vector(N, 0));
for (int j = 0; j < N; j++) {
for (int i = K - 1; i >= 0; i--) {
P[i][j] = P[i + 1][j] + A[i][j];
}
}
vector<vector<vector<long long>>> dp(N, vector(K + 1, vector(K + 1, 0LL)));
for (int a = 0; a <= K; a++) {
for (int b = 0; b <= K; b++) {
if (a < b) {
dp[0][a][b] = P[a][0] - P[b][0];
}
}
}
for (int i = 0; i + 1 < N; i++) {
for (int a = 0; a <= K; a++) {
for (int b = 0; b <= K; b++) {
for (int c = 0; c <= K; c++) {
if (max(a, c) > b) {
dp[i + 1][b][c] = max(dp[i + 1][b][c], dp[i][a][b] + P[b][i + 1] - P[max(a, c)][i + 1]);
} else {
dp[i + 1][b][c] = max(dp[i + 1][b][c], dp[i][a][b]);
}
}
}
}
}
long long ret = 0;
for (int a = 0; a <= K; a++) {
for (int b = 0; b <= K; b++) {
if (a > b) {
dp[N - 1][a][b] = dp[N - 2][a][b] + P[N - 1][b] - P[N - 1][a];
} else {
dp[N - 1][a][b] = dp[N - 2][a][b];
}
ret = max(ret, dp[N - 1][a][b]);
}
}
return ret;
}
