#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
template<typename T>
int len(T &a){
return a.size();
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
std::vector<int> w) {
vector<vector<ll>> s(n + 1, vector<ll> (n + 1));
for(int i = 0; i < m; i ++) s[x[i] + 1][y[i] + 1] = w[i];
for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) s[i][j] += s[i][j - 1];
vector<vector<array<ll, 2>>> dp(n + 1, vector<array<ll, 2>>(n + 1));
for(int i = 2; i <= n; i ++){
for(int j = 0; j <= n; j ++){
for(int k = 0; k < j; k ++){
dp[i][j][0] = max(dp[i][j][0], max(dp[i - 2][k][0], dp[i - 2][k][1]) + s[i - 1][j]);
}
dp[i][j][1] = dp[i][j][0];
for(int k = 0; k <= j; k ++){
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][0] + s[i - 1][j] - s[i - 1][k]);
}
for(int k = j; k <= n; k ++){
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][1] + s[i][k] - s[i][j]);
}
}
}
ll ans = 0;
for(int i = 0; i <= n; i ++){
ans = max({ans, dp[n][i][0], dp[n][i][1]});
}
return ans;
}
