#include <bits/stdc++.h>
#include "fish.h"
// #include "grader.cpp"
using namespace std;
using ll = long long;
ll max_weights(int n, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<ll>> p(n + 1, vector<ll>(n + 1));
for (int i = 0; i < M; i++)
p[++X[i]][++Y[i]] = W[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
p[i][j] += p[i][j - 1];
}
vector<vector<ll>> dp(n + 1, vector<ll>(n + 1)), dp1 = dp;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++) {
if (k < j) dp[i][j] = max(dp[i][j], dp1[i - 1][k]);
else dp[i][j] = max(dp[i][j], dp[i - 1][k] + p[i][k] - p[i][j]);
}
}
for (int j = 0; j <= n; j++) {
for (int k = j; k <= n; k++)
dp1[i][j] = max(dp1[i][j], dp[i - 1][k] + p[i - 1][k] - p[i][j]);
}
}
return *max_element(dp[n].begin(), dp[n].end());
}
