#include "fish.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
using namespace std;
const long long INF = (long long)1e18 + 7;
struct SEG
{
int N;
long long ind[202020];
long long qry(int l, int r)
{
long long ret = 0;
for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
{
if(x & 1) ret = max(ret, ind[x++]);
if(y & 1) ret = max(ret, ind[--y]);
}
return ret;
}
void upd(int x, long long v)
{
x += N;
ind[x] = max(ind[x], v);
while(x >>= 1) ind[x] = max(ind[x << 1], ind[x << 1 | 1]);
}
}dp[2];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
vector<pii> A[N];
for(int i = 0; i < M; ++i) A[X[i]].push_back({Y[i], W[i]});
dp[0].N = dp[1].N = N + 1;
for(int i = 0; i < N; ++i) sort(A[i].begin(), A[i].end());
vector<pii> B[N];
for(int i = 0; i < N; ++i) B[i] = A[i], reverse(B[i].begin(), B[i].end());
for(int i = 1; i < N; ++i)
{
vector<pair<int, long long>> upd[3];
long long ps = 0;
for(auto [y, w] : A[i - 1])
{
ps = max(ps, dp[0].qry(0, y + 1)) + w;
upd[0].push_back({y + 1, ps});
}
ps = 0;
for(auto [y, w] : B[i])
{
ps = max(ps, dp[1].qry(y + 1, N + 1)) + w;
upd[1].push_back({y, ps});
}
ps = 0;
for(auto [y, w] : A[i])
{
ps += w;
upd[2].push_back({y + 1, dp[1].qry(y + 1, N + 1) + ps});
}
upd[0].push_back({0, dp[1].qry(0, N + 1)});
for(auto [x, v] : upd[0]) dp[0].upd(x, v);
for(auto [x, v] : upd[1]) dp[1].upd(x, v);
dp[1].upd(N, dp[0].qry(0, N + 1));
for(auto [x, v] : upd[2]) dp[0].upd(x, v);
// for(int i = 0; i <= N; ++i) cout << dp[0].qry(i, i + 1) << ' '; cout << endl;
// for(int i = 0; i <= N; ++i) cout << dp[1].qry(i, i + 1) << ' '; cout << endl;
}
return max(dp[0].qry(0, N + 1), dp[1].qry(0, N + 1));
}
