#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const ll INF = 1e18;
const int SIZE = 1e5 + 5;
const int K = 10000;
int n;
vector<pair<int, int>> v[SIZE];
ll ans, zero[2], fzero[2], all[2];
vector<pair<int, ll>> inc[2], dek[2];
#define SORTBYTE(TYPE, FR, TO, LEN, BIT) {\
memset(bucket, 0, sizeof(bucket));\
for (auto it = (FR) + LEN; it != (FR); it--)\
++bucket[(it[-1].F >> BIT) & 255];\
for (int *it = bucket; it != bucket + 255; it++)\
it[1] += it[0];\
for (auto it = (FR) + LEN; it != (FR); it--)\
(TO)[--bucket[(it[-1].F >> BIT) & 255]] = it[-1];\
}
int bucket[256];
pair<int, ll> tmp[SIZE];
inline void chmax(ll &x, const ll &y) {
x = max(x, y);
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N;
FOR (i, 0, M - 1) {
X[i]++, Y[i]++;
v[X[i]].pb(Y[i], W[i]);
}
fzero[0] = all[0] = -INF;
FOR (i, 1, n) {
int f = i & 1;
if (v[i].size() >= K) {
SORTBYTE(int, v[i].begin(), tmp, v[i].size(), 0);
SORTBYTE(int, tmp, v[i].begin(), v[i].size(), 8);
SORTBYTE(int, v[i].begin(), tmp, v[i].size(), 16);
SORTBYTE(int, tmp, v[i].begin(), v[i].size(), 24);
} else {
sort(v[i].begin(), v[i].end());
}
zero[f] = fzero[f] = all[f] = -INF;
inc[f].clear(), dek[f].clear();
ll mx = zero[!f], sum = 0;
int pos = 0;
for (auto [j, x] : v[i - 1]) {
while (pos < inc[!f].size() && inc[!f][pos].F < j) {
mx = max(mx, inc[!f][pos].S - sum);
pos++;
}
sum += x;
inc[f].pb(j, sum + mx);
}
while (pos < inc[!f].size() && inc[!f][pos].F < n) {
mx = max(mx, inc[!f][pos].S - sum);
pos++;
}
chmax(all[f], sum + mx);
mx = all[!f], sum = 0, pos = (int) dek[!f].size() - 1;
for (auto [j, x] : v[i]) sum += x;
mx += sum;
for (auto it = v[i].rbegin(); it != v[i].rend(); it++) {
auto [j, x] = *it;
j--;
while (pos >= 0 && dek[!f][pos].F > j) {
mx = max(mx, dek[!f][pos].S + sum);
pos--;
}
sum -= x;
dek[f].pb(j, mx - sum);
}
while (pos >= 0 && dek[!f][pos].F > 0) {
mx = max(mx, dek[!f][pos].S + sum);
pos--;
}
chmax(fzero[f], mx - sum);
reverse(dek[f].begin(), dek[f].end());
chmax(zero[f], zero[!f]);
chmax(zero[f], fzero[!f]);
chmax(all[f], fzero[!f]);
chmax(all[f], all[!f]);
}
int f = n & 1;
ll ans = 0;
chmax(ans, zero[f]);
chmax(ans, fzero[f]);
chmax(ans, all[f]);
return ans;
}
