#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr ll INF = 1e18;
ll max_weights(int N, int M, vt<int> X, vt<int> Y, vt<int> W) {
vt<vt<arl2>> P(N+1);
FOR(i, 0, M-1) {
X[i]++, Y[i]++;
P[X[i]].push_back({Y[i], W[i]});
}
vt<vt<arl2>> dp0(N+1), dp1(N+1);
FOR(i, 0, N) {
P[i].push_back({0, 0});
P[i].push_back({N+1, 0});
sort(all(P[i]));
FOR(j, 1, size(P[i])-1)
P[i][j][1] += P[i][j-1][1];
FOR(j, 0, size(P[i])-1) {
dp0[i].push_back({P[i][j][0]-1, -INF});
dp1[i].push_back({P[i][j][0]-1, -INF});
}
}
dp0[0][0][0] = dp1[0][0][0] = 0;
ll ans = 0;
FOR(i, 1, N) {
int ptr2 = 0, ptr1 = 0;
ll mx = 0;
FOR(x, 0, size(dp0[i]) - 1) {
auto &[j, v0] = dp0[i][x];
auto &[_, v1] = dp1[i][x];
if (i > 1) {
for (; ptr2 < size(dp0[i-2]) && dp0[i-2][ptr2][0] <= j; ptr2++)
mx = max({mx, dp0[i-2][ptr2][1], dp1[i-2][ptr2][1]});
}
for (; ptr1 < size(P[i-1]) && P[i-1][ptr1][0] <= j; ptr1++);
v1 = v0 = max(v0, mx + (ptr1 ? P[i-1][ptr1-1][1] : 0));
}
if (i > 1)
ptr2 = size(dp0[i-2]) - 1;
ptr1 = size(P[i-1]) - 1;
mx = -INF;
ROF(x, size(dp0[i]) - 1, 0) {
auto &[j, v0] = dp0[i][x];
auto &[_, v1] = dp1[i][x];
if (i > 1) {
for (; ptr2 >= 0 && dp0[i-2][ptr2][0] > j; ptr2--) {
for (; ptr1 >= 0 && P[i-1][ptr1][0] > dp0[i-2][ptr2][0]; ptr1--);
mx = max(mx, max(dp0[i-2][ptr2][1], dp1[i-2][ptr2][1]) + (ptr1 >= 0 ? P[i-1][ptr1][1] : 0));
}
}
v1 = v0 = max(v0, mx);
}
ptr1 = 0, ptr2 = 0;
int ptr3 = 0;
mx = -INF;
FOR(x, 0, size(dp0[i]) - 1) {
auto &[j, v0] = dp0[i][x];
for (; ptr1 < size(dp0[i-1]) && dp0[i-1][ptr1][0] <= j; ptr1++) {
for (; ptr2 < size(P[i-1]) && P[i-1][ptr2][0] <= dp0[i-1][ptr1][0]; ptr2++);
mx = max(mx, dp0[i-1][ptr1][1] - (ptr2 ? P[i-1][ptr2-1][1] : 0));
}
for (; ptr3 < size(P[i-1]) && P[i-1][ptr3][0] <= j; ptr3++);
v0 = max(v0, mx + (ptr3 ? P[i-1][ptr3-1][1] : 0));
ans = max(ans, v0);
}
ptr1 = size(dp0[i-1]) - 1;
ptr3 = ptr2 = size(P[i]) - 1;
mx = -INF;
ROF(x, size(dp1[i]) - 1, 0) {
auto &[j, v1] = dp1[i][x];
for (; ptr1 >= 0 && dp0[i-1][ptr1][0] >= j; ptr1--) {
for (; ptr2 >= 0 && P[i][ptr2][0] > dp0[i-1][ptr1][0]; ptr2--);
mx = max(mx, max(dp0[i-1][ptr1][1], dp1[i-1][ptr1][1]) + (ptr2 >= 0 ? P[i][ptr2][1] : 0));
}
for (; ptr3 >= 0 && P[i][ptr3][0] > j; ptr3--);
v1 = max(v1, mx - (ptr3 >= 0 ? P[i][ptr3][1] : 0));
ans = max(ans, v1);
}
}
return ans;
}
/*
ll max_weights(int N, int M, vt<int> X, vt<int> Y, vt<int> W) {
vt<vt<ll>> P(N+1, vt<ll>(N+1));
FOR(i, 0, M-1) {
X[i]++, Y[i]++;
P[X[i]][Y[i]] = W[i];
}
FOR(i, 1, N)
FOR(j, 1, N)
P[i][j] += P[i][j-1];
vt<vt<arl2>> dp(N+1, vt<arl2>(N+1, {-INF, -INF}));
dp[0][0][0] = dp[0][0][1] = 0;
ll ans = 0;
FOR(i, 1, N)
FOR(j, 0, N) {
FOR(k, 0, j)
dp[i][j][0] = max(dp[i][j][0], (i > 1 ? max(dp[i-2][k][0], dp[i-2][k][1]) : 0) + P[i-1][j]);
FOR(k, j+1, N)
dp[i][j][0] = max(dp[i][j][0], (i > 1 ? max(dp[i-2][k][0], dp[i-2][k][1]) : -INF) + P[i-1][k]);
dp[i][j][1] = dp[i][j][0];
FOR(k, 0, j)
dp[i][j][0] = max(dp[i][j][0], dp[i-1][k][0] + P[i-1][j] - P[i-1][k]);
FOR(k, j, N)
dp[i][j][1] = max(dp[i][j][1], max(dp[i-1][k][0], dp[i-1][k][1]) + P[i][k] - P[i][j]);
ans = max({ans, dp[i][j][0], dp[i][j][1]});
}
return ans;
}*/
