#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const ll INF = 1e18;
int N, M;
vector<pii> V[MAXN+10];
vector<ll> dp1[MAXN+10], dp2[MAXN+10];
struct BIT
{
ll tree[MAXN+10];
void init() { for(int i=1; i<=N; i++) tree[i]=-INF; }
void update(int i, ll k) { for(; i<=N; i+=(i&-i)) tree[i]=max(tree[i], k); }
ll query(int i) { ll ret=-INF; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; }
}bit1, bit2;
ll max_weights(int _N, int _M, vector<int> _X, vector<int> _Y, vector<int> _W)
{
N=_N; M=_M;
for(int i=0; i<M; i++)
{
int x=_X[i]+1, y=_Y[i]+1, w=_W[i];
V[x].push_back({y, w});
}
for(int i=0; i<=N+1; i++)
{
sort(V[i].begin(), V[i].end());
if(V[i].empty() || V[i][0].first!=1) V[i].push_back({1, 0});
if(V[i].back().first!=N) V[i].push_back({N, 0});
sort(V[i].begin(), V[i].end());
dp1[i]=vector<ll>(V[i].size(), -INF);
dp2[i]=vector<ll>(V[i].size(), -INF);
}
bit1.init(); bit2.init();
dp2[0][0]=0; dp1[0][dp1[0].size()-1]=0;
ll p=-INF, q=-INF, ans=0;
for(int i=0; i<=N+1; i++)
{
int t=V[i].size();
if(i-1>=0) p=max(p, dp2[i-1][0]);
if(i-2>=0) q=max(q, dp1[i-2].back());
dp1[i][0]=max(dp1[i][0], p+V[i][0].second);
if(i-2>=0) dp1[i][0]=max(dp1[i][0], dp1[i-2].back()+V[i][0].second);
dp2[i][t-1]=max(dp2[i][t-1], q+V[i][t-1].second);
for(int j=0; j<t; j++)
{
auto [y, w] = V[i][j];
dp1[i][j]=max(dp1[i][j], bit1.query(y-1)+w);
bit1.update(y, dp1[i][j]);
}
for(int j=t-1; j>=0; j--)
{
auto [y, w] = V[i][j];
dp2[i][j]=max(dp2[i][j], bit2.query(N-y)+w);
bit2.update(N-y+1, dp2[i][j]);
}
ans=max(ans, dp2[i][0]);
// for(auto it : dp1[i]) printf("%lld ", it); printf("\n");
// for(auto it : dp2[i]) printf("%lld ", it); printf("\n");
// printf("\n");
}
return ans;
}
