#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int64 max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
// dp[i][prev][secprev] = at row i, previous row was built to height `prev`,
// even before that was height `secprev`
for (int &i : Y) {
i++;
}
const int ht = *max_element(Y.begin(), Y.end());
vector grid(N + 1, vector<int64>(ht + 1));
for (int i = 0; i < M; ++i) {
grid[X[i]][Y[i]] += W[i];
}
for (int i = 0; i < N; ++i) {
partial_sum(grid[i].begin(), grid[i].end(), grid[i].begin());
}
vector dp(N + 1, vector(ht + 1, vector<int64>(ht + 1)));
for (int i = N - 1; i >= 0; --i) {
for (int p1 = 0; p1 <= ht; ++p1) {
for (int p2 = 0; p2 <= ht; ++p2) {
int cut = max(p1, p2);
{
for (int cur = 0; cur <= min(cut, p1); ++cur) {
dp[i][p1][p2] = max(dp[i][p1][p2], dp[i + 1][cur][p1] + grid[i + 1][cur] - grid[i][cur]);
}
if (i == 0) {
for (int cur = cut + 1; cur <= p1; ++cur) {
dp[i][p1][p2] = max(dp[i][p1][p2], dp[i + 1][cur][p1] + grid[i + 1][cur] - grid[i][cur]);
}
} else {
for (int cur = cut + 1; cur <= p1; ++cur) {
dp[i][p1][p2] = max(dp[i][p1][p2], dp[i + 1][cur][p1] + grid[i + 1][cur] - grid[i][cur] + grid[i - 1][cur] - grid[i - 1][cut]);
}
}
}
{
for (int cur = p1 + 1; cur <= min(cut, ht); ++cur) {
dp[i][p1][p2] = max(dp[i][p1][p2], dp[i + 1][cur][p1] + grid[i + 1][cur] - grid[i][p1]);
}
if (i == 0) {
for (int cur = cut + 1; cur <= ht; ++cur) {
dp[i][p1][p2] = max(dp[i][p1][p2], dp[i + 1][cur][p1] + grid[i + 1][cur] - grid[i][p1]);
}
} else {
for (int cur = cut + 1; cur <= ht; ++cur) {
dp[i][p1][p2] = max(dp[i][p1][p2], dp[i + 1][cur][p1] + grid[i + 1][cur] - grid[i][p1] + grid[i - 1][cur] - grid[i - 1][cut]);
}
}
}
}
}
}
return dp[0][0][0];
}
