#include "fish.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<vector<ll>> a(n, vector<ll>(n));
for (int i = 0; i < m; i++) {
a[x[i]][y[i]] = w[i];
}
vector<vector<ll>> pref(n, vector<ll>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j == 0)
pref[i][j] = a[i][j];
else
pref[i][j] = pref[i][j - 1] + a[i][j];
}
}
vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(10, vector<ll>(10, -1e18)));
for (int i = 0; i <= min(n, 8 + 1); i++) {
dp[0][i][0] = 0;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= min(n, 8 + 1); j++) {
for (int k = 0; k <= min(n, 8 + 1); k++) {
for (int c = 0; c <= min(n, 8 + 1); c++) {
if (max(c, j) <= k)
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][c]);
else if (k != 0)
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][c] + pref[i - 1][max(c, j) - 1] - pref[i - 1][k - 1]);
else
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][c] + pref[i - 1][max(c, j) - 1]);
}
}
}
}
ll ans = 0;
for (int j = 0; j <= min(n, 8 + 1); j++) {
for (int k = 0; k <= min(n, 8 + 1); k++) {
ans = max(ans, dp[n - 1][j][k]);
}
}
return ans;
}
