#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
auto n = N, m = M;
auto x = X, y = Y, w = W;
if (n == 1)
return 0;
// vector<int> ord(m);
// iota(ord.begin(), ord.end(), 0);
// sort(ord.begin(), ord.end(), [&](int l, int r)
// { return x[l] < x[r]; });
vector cnt(n, vector<int>(n));
for (int i = 0; i < m; i++)
{
cnt[y[i]][x[i]] = w[i];
}
vector pref(n, vector<ll>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
pref[i][j] = cnt[i][j];
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
pref[j][i] += pref[j - 1][i];
vector dp(n, vector<ll>(n + 1, -1));
// dp[i][j] = i is the current cell, j is the current height
auto rec = [&](auto self, int i, int j) -> ll
{
if (i == n)
return 0;
auto &ret = dp[i][j];
if (~ret)
return ret;
ret = self(self, i + 1, 0) + (j ? pref[j - 1][i] : 0);
for (int k = 0; k < j - 1; k++)
ret = max(ret, self(self, i + 1, k + 1) + pref[j - 1][i] - pref[k][i]);
for (int k = j - 1; k < n; k++)
ret = max(ret, self(self, i + 1, k + 1));
if (i + 1 < n)
{
for (int k = 1; k <= n; k++)
ret = max(ret, self(self, i + 2, k) + pref[k - 1][i]);
}
return ret;
};
return rec(rec, 0, 0);
}
