#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second
void maxs(ll &a, ll b) {
if (a < b) a = b;
}
long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
for (int i = 0; i < m; i++) Y[i]++;
vector pre(n, vector(n + 1, 0ll));
for (int i = 0; i < m; i++) pre[X[i]][Y[i]] += W[i];
for (int i = 0; i < n; i++) {
for (int j = 1; j <= n; j++) pre[i][j] += pre[i][j - 1];
}
vector dp(n, vector(n + 1, make_pair(0ll, 0ll)));
// dp[i][j] - birinchi i'ta qatorni hisobga osak ohirgi qatorni boyi j bosa max javob
// ff - o'zinikini qo'shilgan, ss - o'ziniki qo'shilmagan
for (int i = 1; i < n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= j and i > 0; k++) {
maxs(dp[i][j].ss, dp[i - 1][k].ss + pre[i - 1][j] - pre[i - 1][k]);
maxs(dp[i][j].ss, dp[i - 1][k].ff);
}
for (int k = j + 1; k <= n and i > 0; k++) {
maxs(dp[i][j].ff, dp[i - 1][k].ff + pre[i][k] - pre[i][j]);
maxs(dp[i][j].ss, dp[i - 1][k].ff);
}
for (int k = 0; k <= n and i > 1; k++) {
maxs(dp[i][j].ss, dp[i - 2][k].ff + pre[i - 1][max(j, k)]);
}
for (int k = 0; k <= n and i > 2; k++) {
maxs(dp[i][j].ss, dp[i - 3][k].ff + pre[i - 2][k] + pre[i - 1][j]);
}
maxs(dp[i][j].ff, dp[i][j].ss);
// maxlash esdan chiqmasin
}
}
ll ans = 0;
for (int i = 0; i < n; i++) maxs(ans, dp[n - 1][i].ff);
return ans;
}
// g++ -o fish -O2 fish.cpp grader.cpp -std=c++20 && .\fish < input.txt > output.txt
