#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 inf = 1e15;
class segment_tree {
int n;
vector<int64> seg;
public:
segment_tree(int n) : n(n), seg(2 * n, -inf) {}
void set(int i, int64 x) {
for (seg[i += n] = x, i >>= 1; i > 0; i >>= 1) {
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
}
int64 query(int l, int r) {
int64 ans = -inf;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = max(ans, seg[l++]);
if (r & 1) ans = max(ans, seg[--r]);
}
return ans;
}
};
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)));
vector sts1(N + 1, vector(ht + 1, segment_tree(ht + 1)));
vector sts2(N + 1, vector(ht + 1, segment_tree(ht + 1)));
vector sts3(N + 1, vector(ht + 1, segment_tree(ht + 1)));
vector sts4(N + 1, vector(ht + 1, segment_tree(ht + 1)));
for (int i = N; i >= 0; --i) {
for (int p1 = 0; p1 <= ht; ++p1) {
for (int p2 = 0; p2 <= ht; ++p2) {
if (i != N) {
int cut = max(p1, p2);
dp[i][p1][p2] = max(dp[i][p1][p2], sts1[i + 1][p1].query(0, min(cut, p1)));
if (i == 0) {
dp[i][p1][p2] = max(dp[i][p1][p2], sts1[i + 1][p1].query(cut + 1, p1));
} else {
dp[i][p1][p2] = max(dp[i][p1][p2], sts4[i + 1][p1].query(cut + 1, p1) - grid[i - 1][cut]);
}
dp[i][p1][p2] = max(dp[i][p1][p2], sts2[i + 1][p1].query(p1 + 1, min(cut, ht)) - grid[i][p1]);
if (i == 0) {
dp[i][p1][p2] = max(dp[i][p1][p2], sts2[i + 1][p1].query(cut + 1, ht) - grid[i][p1]);
} else {
dp[i][p1][p2] = max(dp[i][p1][p2], sts3[i + 1][p1].query(cut + 1, ht) - grid[i - 1][cut] - grid[i][p1]);
}
}
if (i >= 1) {
sts1[i][p2].set(p1, dp[i][p1][p2] + grid[i][p1] - grid[i - 1][p1]);
sts2[i][p2].set(p1, dp[i][p1][p2] + grid[i][p1]);
}
if (i >= 2) {
sts3[i][p2].set(p1, dp[i][p1][p2] + grid[i][p1] + grid[i - 2][p1]);
sts4[i][p2].set(p1, dp[i][p1][p2] + grid[i][p1] - grid[i - 1][p1] + grid[i - 2][p1]);
}
}
}
}
return dp[0][0][0];
}
