#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
using ll = long long;
#define int ll
int maxY = *max_element(Y.begin(), Y.end()) + 2;
vector<vector<int>> colPrefSum(N, vector<int>(N));
vector<vector<int>> fish(N, vector<int>(N));
for (int i = 0; i < M; ++i) {
fish[X[i]][Y[i]] = W[i];
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
colPrefSum[i][j] = (j ? colPrefSum[i][j-1] : 0) + fish[i][j];
}
}
auto range_sum = [&](int x, int l, int r) {
if (x < 0) return 0ll;
if (l < 0) return 0ll;
return colPrefSum[x][r] - (l ? colPrefSum[x][l-1] : 0ll);
};
vector<vector<int>> dp_prev(maxY, vector<int>(maxY));
vector<vector<int>> dp_curr(maxY, vector<int>(maxY));
for (int i = 0; i < N; ++i) {
swap(dp_prev, dp_curr);
for (int j = 0; j < maxY; ++j) {
for (int k = 0; k < maxY; ++k) {
dp_curr[j][k] = 0;
for (int l = 0; l < maxY; ++l) {
if (j < k) {
dp_curr[j][k] = max(dp_curr[j][k], dp_prev[l][j] + max(range_sum(i-1, max(l, j) - 1, k), 0ll));
}
else {
dp_curr[j][k] = max(dp_curr[j][k], dp_prev[l][j] + range_sum(i, j-1, k));
}
}
}
}
}
int ans = -1e18 - 5;
for (int i = 0; i < maxY; ++i) for (int j = 0; j < maxY; ++i) ans = max(ans, dp_curr[i][j]);
return ans;
}
