#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, 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) {
for (int cur = 0; cur <= ht; ++cur) {
int64 base = 0;
// delete stuff got by p1 but we fucked
base -= grid[i][min(p1, cur)];
// in column i-1, get stuff from max(p1,p2)+1 to cur
if (i - 1 >= 0 && max(p1, p2) + 1 <= cur) {
base += grid[i - 1][cur] - grid[i - 1][max(p1, p2)];
}
// in column i+1, get stuff from 0 to cur
if (i + 1 < N) {
base += grid[i + 1][cur];
}
dp[i][p1][p2] = max(dp[i][p1][p2], dp[i + 1][cur][p1] + base);
}
}
}
}
return dp[0][0][0];
}
