#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];
int m2 = min(n + 1, *max_element(y.begin(), y.end()) + 2);
vector dp(n, vector(m2, vector<ll>(m2, -1)));
// dp[i][j] = i is the current cell, j is the current height
auto rec = [&](auto self, int i, int j, int k) -> ll
{
if (i == n)
return 0;
auto &ret = dp[i][j][k];
if (~ret)
return ret;
ret = 0;
if(i == n-1)
{
return max(0ll, (j ? pref[j - 1][i] : 0) - (k ? pref[k - 1][i] : 0));
}
for(int l = 0; l < m2; l++)
ret = max(ret, self(self, i + 1, k, l) + max(0ll, (max(j, l) ? pref[max(j, l) - 1][i] : 0) - (k ? pref[k - 1][i] : 0)));
return ret;
};
for(int i = 0; i < m2; i++)
rec(rec, 0, 0, i);
ll mx = 0;
for(auto i: dp)
for(auto j: i)
for(auto k: j)
mx = max(mx, k);
return mx;
}
