#include <bits/stdc++.h>
using namespace std;
namespace {
using int64 = long long;
const int64 inf = 1e15;
}; // namespace
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) {
for (int j = 1; j <= ht; ++j) {
grid[i][j] += grid[i][j - 1];
}
}
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) {
vector<int64> pref1(ht + 1), suff1(ht + 1), pref2(ht + 1), suff2(ht + 1), pref3(ht + 1), suff3(ht + 1), pref4(ht + 1), suff4(ht + 1);
for (int x = 0; x <= ht; ++x) {
pref1[x] = suff1[x] = dp[i + 1][x][p1] + grid[i + 1][x] - grid[i][x];
pref2[x] = suff2[x] = dp[i + 1][x][p1] + grid[i + 1][x];
if (i != 0) {
pref3[x] = suff3[x] = dp[i + 1][x][p1] + grid[i + 1][x] + grid[i - 1][x];
pref4[x] = suff4[x] = dp[i + 1][x][p1] + grid[i + 1][x] - grid[i][x] + grid[i - 1][x];
}
}
for (int x = 1; x <= ht; ++x) {
pref1[x] = max(pref1[x], pref1[x - 1]);
pref2[x] = max(pref2[x], pref2[x - 1]);
pref3[x] = max(pref3[x], pref3[x - 1]);
pref4[x] = max(pref4[x], pref4[x - 1]);
}
for (int x = ht - 1; x >= 0; --x) {
suff1[x] = max(suff1[x], suff1[x + 1]);
suff2[x] = max(suff2[x], suff2[x + 1]);
suff3[x] = max(suff3[x], suff3[x + 1]);
suff4[x] = max(suff4[x], suff4[x + 1]);
}
{
for (int p2 = 0; p2 <= p1; ++p2) {
dp[i][p1][p2] = max(dp[i][p1][p2], pref1[p1]);
if (i == 0) {
if (p1 + 1 <= ht) dp[i][p1][p2] = max(dp[i][p1][p2], suff2[p1 + 1] - grid[i][p1]);
} else {
if (p1 + 1 <= ht) dp[i][p1][p2] = max(dp[i][p1][p2], suff3[p1 + 1] - grid[i - 1][p1] - grid[i][p1]);
}
}
int64 val = -inf;
for (int p2 = p1 + 1; p2 <= ht; ++p2) {
val = max(val, dp[i + 1][p2][p1]);
dp[i][p1][p2] = max(dp[i][p1][p2], pref1[p1]);
if (p2 <= ht) {
dp[i][p1][p2] = max(dp[i][p1][p2], val - grid[i][p1]);
} else {
if (p1 + 1 <= ht) dp[i][p1][p2] = max(dp[i][p1][p2], suff2[p1 + 1] - grid[i][p1]);
}
if (i == 0) {
if (p2 + 1 <= ht) dp[i][p1][p2] = max(dp[i][p1][p2], suff2[p2 + 1] - grid[i][p1]);
} else {
if (p2 + 1 <= ht) dp[i][p1][p2] = max(dp[i][p1][p2], suff3[p2 + 1] - grid[i - 1][p2] - grid[i][p1]);
}
}
}
}
}
return dp[0][0][0];
}
