#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<ll> pref1(n+1, 0), pref2(n+1, 0);
vector<vector<array<ll, 2>>> fish(n+1);
vector<vector<ll>> dp(n+1, vector<ll>(n+1, 0));
for(int i = 0; i < m; i++) {
fish[x[i]].push_back({y[i], w[i]});
}
for(int i = 0; i < n; i++) sort(fish[i].begin(), fish[i].end());
for(auto [Y, W] : fish[0]) {
pref1[Y] = W;
}
for(auto [Y, W] : fish[1]) {
pref2[Y] = W;
}
for(int i = 1; i <= n; i++) {
pref1[i] += pref1[i-1];
pref2[i] += pref2[i-1];
}
for(int j = 0; j <= n; j++) {
for(int k = 0; k <= n; k++) {
ll f = 0;
if(k > j) f += (k == 0 ? 0 : pref2[k-1]) - (j == 0 ? 0 : pref2[j-1]);
else f += (j == 0 ? 0 : pref1[j-1]) - (k == 0 ? 0 : pref1[k-1]);
dp[1][j] = max(dp[1][j], f);
}
}
swap(pref2, pref1);
for(int i = 2; i < n; i++) {
for(int j = 0; j <= n; j++) pref2[j] = 0;
for(auto [Y, W] : fish[i]) {
pref2[Y] = W;
}
for(int j = 1; j <= n; j++) pref2[j] += pref2[j-1];
for(int j = 0; j <= n; j++) {
for(int k = 0; k <= n; k++) {
ll f = dp[i-1][k], s = dp[i-2][k];
if(k != 0 || j != 0) {
s += pref1[max(j, k) - 1];
}
if(k > j) {
f += (k == 0 ? 0 : pref2[k-1]) - (j == 0 ? 0 : pref2[j-1]);
}
dp[i][j] = max({dp[i][j], f, s});
}
}
swap(pref1, pref2);
}
ll ans = 0;
for(int i = 0; i <= n; i++) {
ans = max(ans, dp[n-1][i]);
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3});
}*/
