#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++) {
ll mx = -1e18, mx2 = -1e18, mx3 = -1e18;
for (int j = 0; j <= n; j++) {
maxs(mx, dp[i - 1][j].ss - pre[i - 1][j]);
maxs(mx2, dp[i - 1][j].ff);
maxs(dp[i][j].ss, max(mx + pre[i - 1][j], mx2));
// maxs(mx3, dp[i - 2][j])
for (int k = 0; k <= j and i > 1; k++) {
maxs(dp[i][j].ss, dp[i - 2][k].ff + pre[i - 1][j]);
}
for (int k = j + 1; k <= n and i > 1; k++) {
maxs(dp[i][j].ss, dp[i - 2][k].ff + pre[i - 1][k]);
}
}
mx = -1e18;
for (int j = 0; j <= n and i > 2; j++) {
maxs(mx, dp[i - 3][j].ff + pre[i - 2][j]);
}
for (int j = 0; j <= n; j++) maxs(dp[i][j].ss, mx + pre[i - 1][j]);
mx = -1e18, mx2 = -1e18;
for (int j = n; j >= 0; j--) {
maxs(dp[i][j].ff, mx - pre[i][j]);
maxs(dp[i][j].ss, mx2);
maxs(mx, dp[i - 1][j].ff + pre[i][j]);
maxs(mx2, dp[i - 1][j].ff);
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
