#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
const int MAX = 1e5 + 5, SINF = 2e9;
const long long INF = 1e18;
bool markLow[MAX];
vector<ii> g[MAX];
vector<long long> S[MAX];
vector<vector<long long>> f[MAX];
struct FenwickTreeLow {
int n;
vector<int> buffer;
vector<long long> tree;
FenwickTreeLow(int _n) {
n = _n;
tree.resize(n + 5, -INF);
}
void update(int idx, long long val) {
idx++;
for (int i = idx; i <= n; i += i & -i) {
buffer.push_back(i);
tree[i] = max(tree[i], val);
}
}
long long get(int idx) {
idx++;
long long rs = 0;
for (int i = idx; i > 0; i -= i & -i)
rs = max(rs, tree[i]);
return rs;
}
void reset() {
for (int id: buffer)
tree[id] = -INF;
buffer.clear();
}
};
struct FenwickTreeHigh {
int n;
vector<int> buffer;
vector<long long> tree;
FenwickTreeHigh(int _n) {
n = _n;
tree.resize(n + 5, -INF);
}
void update(int idx, long long val) {
idx++;
for (int i = idx; i > 0; i -= i & -i) {
buffer.push_back(i);
tree[i] = max(tree[i], val);
}
}
long long get(int idx) {
idx++;
long long rs = 0;
for (int i = idx; i <= n; i += i & -i)
rs = max(rs, tree[i]);
return rs;
}
void reset() {
for (int id: buffer)
tree[id] = -INF;
buffer.clear();
}
};
long long calcCostLeft(int col, int L) {
int l = lower_bound(g[col].begin(), g[col].end(), ii(L, 0)) - g[col].begin();
return l ? S[col][l - 1] : 0;
}
long long calcCostRight(int col, int R) {
int r = upper_bound(g[col].begin(), g[col].end(), ii(R, 0)) - g[col].begin() - 1;
return r >= 0 ? S[col][r] : 0;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int i = 0; i < M; i++) {
g[X[i]].emplace_back(Y[i], W[i]);
if (!Y[i])
markLow[X[i]] = true;
}
for (int i = 0; i < N; i++) {
if (!markLow[i])
g[i].emplace_back(0, 0);
g[i].emplace_back(N, 0);
}
for (int i = 0; i < N; i++) {
sort(g[i].begin(), g[i].end());
S[i].resize(g[i].size());
S[i][0] = g[i][0].second;
for (int j = 1; j < g[i].size(); j++)
S[i][j] = S[i][j - 1] + g[i][j].second;
f[i].resize(g[i].size(), vector<long long>(2));
}
FenwickTreeLow lowTree(N + 5), lowJump(N + 5);
FenwickTreeHigh highTree(N + 5), highJump(N + 5);
long long rs = 0;
for (int i = 1; i < N; i++) {
if (i > 1) {
lowJump.reset(), highJump.reset();
for (int t = 0; t < g[i - 2].size(); t++) {
lowJump.update(t, f[i - 2][t][1]);
highJump.update(t, f[i - 2][t][1] + calcCostRight(i - 1, g[i - 2][t].first));
}
}
lowTree.reset(), highTree.reset();
for (int t = 0; t < g[i - 1].size(); t++) {
lowTree.update(t, f[i - 1][t][0] - calcCostLeft(i - 1, g[i - 1][t].first));
highTree.update(t, f[i - 1][t][1] + calcCostRight(i, g[i - 1][t].first));
}
for (int j = 0; j < g[i].size(); j++) {
if (i > 1) {
int low = upper_bound(g[i - 2].begin(), g[i - 2].end(), ii(g[i][j].first, SINF)) - g[i - 2].begin() - 1;
long long tmp = lowJump.get(low) + calcCostRight(i - 1, g[i][j].first);
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
int high = low + 1;
tmp = highJump.get(high);
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
} else {
long long tmp = calcCostRight(0, g[i][j].first);
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
}
int low = upper_bound(g[i - 1].begin(), g[i - 1].end(), ii(g[i][j].first, SINF)) - g[i - 1].begin() - 1;
long long tmp = lowTree.get(low) + calcCostRight(i - 1, g[i][j].first);
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
int high = lower_bound(g[i - 1].begin(), g[i - 1].end(), ii(g[i][j].first, 0)) - g[i - 1].begin();
f[i][j][1] = max(f[i][j][1], highTree.get(high) - calcCostLeft(i, g[i][j].first));
rs = max({rs, f[i][j][0], f[i][j][1]});
}
}
return rs;
}
