#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
vector<vector<ll>> vals(N, vector<ll>(N + 1, 0));
for (int i = 0; i < M; ++i) vals[X[i]][Y[i] + 1] += W[i];
for (int i = 0; i < N; ++i) {
for (int j = 1; j <= N; ++j) vals[i][j] += vals[i][j - 1];
}
vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(N + 1, vector<ll>(N + 1, 0)));
for (int i = 0; i <= N; ++i) {
for (int j = 0; j <= N; ++j) {
if (!i && !j) continue;
dp[0][i][j] = LLONG_MIN / 2;
}
}
for (int i = 0; i < N; ++i) {
vector<vector<ll>> &prevDp = dp[i], &curDp = dp[i + 1];
for (int prev = 0; prev <= N; ++prev) {
ll cumulative = LLONG_MIN / 2, otherwise = LLONG_MIN / 2;
for (int prev2 = 0; prev2 <= N; ++prev2) {
cumulative = max(prevDp[prev2][prev], cumulative);
if (i) otherwise = max(otherwise, prevDp[prev2][prev] - vals[i - 1][max(prev2, prev)]);
}
for (int cur = 0; cur <= N; ++cur) {
// ll additional = max(0ll, vals[i][prev] - vals[i][cur]);
// if (i && cur > max(prev2, prev)) additional += vals[i - 1][cur] - vals[i - 1][max(prev2, prev)];
ll curBest = cumulative;
if (i) curBest = max(curBest, vals[i - 1][cur] + otherwise);
curDp[prev][cur] = max(curDp[prev][cur], curBest + max(0ll, vals[i][prev] - vals[i][cur]));
}
}
}
// for (auto &i : dp) {
// for (auto &j : i) {
// for (auto &k : j) cout << k << ' ';
// cout << '\n';
// }
// cout << '\n';
// }
ll res = 0;
for (int i = 0; i <= N; ++i) {
for (int j = 0; j <= N; ++j) res = max(res, dp[N][i][j]);
}
return res;
}
