#include "fish.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <array>
#pragma GCC optimize("O3")
using namespace std;
// #define mxn 5000
// long long dp[mxn+2][mxn+2][2];
// long long p[mxn+2][mxn+2];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
int n = N, m = M;
vector<vector<int>> c(n+2);
vector<map<int, long long>> p(n+2);
for (auto &mp: p) mp[0] = mp[n] = 0;
for (int i=0; i<m; i++) {
int x = X[i], y = Y[i], w = W[i];
x++, y++;
c[x].push_back(y);
p[x][y] += w;
}
for (auto &v: c) {
v.push_back(0);
v.push_back(n);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
v.resize(n+1);
iota(v.begin(), v.end(), 0);
}
for (int i=0; i<=n; i++) {
long long pre = 0;
for (auto &[key, val]: p[i]) {
pre += val;
val = pre;
}
// partial_sum(p[i], p[i]+n+1, p[i]);
}
vector<map<int, long long>> dp0(n+2);
vector<map<int, long long>> dp1(n+2);
// for (int j=1; j<=n; j++) dp[0][j][0] = dp[0][j][1] = -1e18;
dp0[0][1] = dp1[0][n] = -1e18;
dp0[0][0] = dp1[0][0] = 0;
auto get = [&] (int i, int j, int ty) -> long long {
if (ty == 1) {
j = *lower_bound(c[i].begin(), c[i].end(), j);
return dp1[i][j];
}else{
j = *prev(upper_bound(c[i].begin(), c[i].end(), j));
return dp0[i][j];
}
};
auto pre = [&] (int i, int j) -> long long {
if (j < 0) return 0;
return prev(p[i].upper_bound(j))->second;
};
long long ans = 0;
auto reversed = [] (vector<int> v) {
reverse(v.begin(), v.end());
return v;
};
for (int i=1; i<=n; i++) {
{
long long mx0 = 0;
for (int j: c[i]) {
long long prefix = pre(i-1, j);
mx0 = max(mx0, (get(i-1, j, 0) - prefix));
dp0[i][j] = max(dp0[i][j], prefix + mx0);
}
}
if (i > 1) {
long long mx0 = 0;
for (int j: c[i]) {
mx0 = max(mx0, get(i-2, j, 1));
dp0[i][j] = max(dp0[i][j], mx0 + pre(i-1, j));
}
long long mx1 = 0;
for (int j: reversed(c[i])) {
mx1 = max(mx1, get(i-2, j, 1) + pre(i-1, j));
dp0[i][j] = max(dp0[i][j], mx1);
}
}
{
long long mx1 = 0;
for (int j: reversed(c[i])) {
long long prefix = pre(i, j);
mx1 = max(mx1, get(i-1, j, 1) + prefix);
dp1[i][j] = max(dp1[i][j], mx1 - prefix);
dp1[i][j] = max(dp1[i][j], dp0[i][j]);
ans = max(ans, dp1[i][j]);
}
}
}
return ans;
}
