#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;
int n, m;
vector<pair<int, int> > v[N];
vector<ll> dp0[N], dp1[N];
long long max_weights(int NN, int MM, std::vector<int> XX, std::vector<int> YY, std::vector<int> WW)
{
n = NN;
m = MM;
for (int i = 0; i < m; ++i)
{
v[XX[i] + 1].push_back(m_p(YY[i], WW[i]));
}
v[0].push_back(m_p(0, 0));
for (int i = 1; i <= n; ++i)
{
sort(all(v[i]));
v[i].push_back(m_p(n, 0));
}
dp0[0].push_back(0);
dp1[0].push_back(0);
for (int i = 1; i <= n; ++i)
{
ll maxu = 0;
for (int j = 0; j < sz(v[i - 1]); ++j)
{
maxu = max(maxu, dp0[i - 1][j]);
}
dp0[i].assign(sz(v[i]), maxu);
dp1[i].assign(sz(v[i]), maxu);
vector<ll> p;
p.assign(sz(v[i]), 0);
p[0] = v[i][0].se;
for (int j = 1; j < sz(v[i]); ++j)
p[j] = p[j - 1] + v[i][j].se;
int k = sz(v[i - 1]) - 1;
maxu = 0;
for (int j = sz(v[i]) - 1; j >= 0; --j)
{
while (k >= 0 && v[i - 1][k].fi > v[i][j].fi)
{
maxu = max(maxu, p[j] + dp0[i - 1][k]);
--k;
}
if (j)
dp0[i][j] = max(dp0[i][j], maxu - p[j - 1]);
else
dp0[i][j] = max(dp0[i][j], maxu);
}
k = 0;
maxu = 0;
ll pp = 0;
for (int j = 0; j < sz(v[i]); ++j)
{
while (k < sz(v[i - 1]) && v[i - 1][k].fi < v[i][j].fi)
{
maxu = max(maxu, dp1[i - 1][k] - pp);
pp += v[i - 1][k].se;
++k;
}
dp1[i][j] = max(dp1[i][j], pp + maxu);
}
for (int j = 0; j < sz(v[i]); ++j)
dp0[i][j] = max(dp0[i][j], dp1[i][j]);
}
ll ans = 0;
for (int j = 0; j < sz(v[n]); ++j)
{
ans = max(ans, dp0[n][j]);
}
return ans;
}
