#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
// every conponent can only be decreasing and increasing (except for the first and last, they can only be inc/decreasing).
vector<pll> pos[100005];
vector<ll> up[100005], down[100005];
ll non[100005], sz[100005];
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
for (int i = 0; i < M; i++)
pos[X[i] + 1].emplace_back(pll(Y[i], W[i]));
pos[0] = {pll(-1, 0)};
for (int i = 1; i <= N; i++)
{
sz[0] = 1;
sort(pos[i].begin(), pos[i].end());
sz[i] = pos[i].size();
}
up[0] = {0};
down[0] = {(ll)-1e18};
non[0] = -1e18;
for (int i = 1; i <= N; i++)
{
up[i].resize(sz[i]);
down[i].resize(sz[i]);
non[i] = max(0LL, non[i - 1]);
if (!down[i - 1].empty())
non[i] = max(non[i], down[i - 1].front());
if (!up[i - 1].empty())
non[i] = max(non[i], up[i - 1].back());
{
ll acc = non[i - 1];
for (int j = sz[i] - 1, k = sz[i - 1] - 1; j >= 0; j--)
{
while (k >= 0 && pos[i - 1][k].F > pos[i][j].F)
acc = max(acc, down[i - 1][k]), k--;
down[i][j] = acc + pos[i][j].S;
acc = max(acc, down[i][j]);
}
}
{
ll acc = non[i - 1];
if (!down[i - 1].empty())
acc = max(acc, down[i - 1].front());
for (int j = 0, k = 0; j < sz[i]; j++)
{
while (k < sz[i - 1] && pos[i - 1][k].F < pos[i][j].F)
acc = max(acc, up[i - 1][k]), k++;
up[i][j] = acc + pos[i][j].S;
acc = max(acc, up[i][j]);
}
}
}
ll ans = non[N];
if (!down[N].empty())
ans = max(ans, down[N].front());
return ans;
}
