#include "fish.h"
#include <bits/stdc++.h>
#define INF (ll)(1e16)
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef pair<int, int> pll;
struct Node { int l, r; ll val; };
struct SEG1 {
vector<Node> seg[100005];
void update(int str, int ed, int idx, ll val, int i, int node) {
if(str == ed) { seg[i][node].val = val; return; }
int mid = str + ed >> 1;
if(idx <= mid) {
if(seg[i][node].l == -1) {
seg[i].push_back({-1, -1, -INF});
seg[i][node].l = seg[i].size() - 1;
}
update(str, mid, idx, val, i, seg[i][node].l);
}
else {
if(seg[i][node].r == -1) {
seg[i].push_back({-1, -1, -INF});
seg[i][node].r = seg[i].size() - 1;
}
update(mid + 1, ed, idx, val, i, seg[i][node].r);
}
seg[i][node].val = -INF;
if(seg[i][node].l != -1) seg[i][node].val = max(seg[i][node].val, seg[i][seg[i][node].l].val);
if(seg[i][node].r != -1) seg[i][node].val = max(seg[i][node].val, seg[i][seg[i][node].r].val);
}
ll query(int str, int ed, int left, int right, int i, int node) {
if(node == -1) return -INF;
if(str > right || ed < left) return -INF;
if(left <= str && ed <= right) return seg[i][node].val;
int mid = str + ed >> 1;
return max(query(str, mid, left, right, i, seg[i][node].l), query(mid + 1, ed, left, right, i, seg[i][node].r));
}
} seg1, seg2, seg3;
struct SEG2 {
vector<Node> seg[100005];
void update(int str, int ed, int idx, ll val, int i, int node) {
if(str == ed) { seg[i][node].val = val; return; }
int mid = str + ed >> 1;
if(idx <= mid) {
if(seg[i][node].l == -1) {
seg[i].push_back({-1, -1, 0});
seg[i][node].l = seg[i].size() - 1;
}
update(str, mid, idx, val, i, seg[i][node].l);
}
else {
if(seg[i][node].r == -1) {
seg[i].push_back({-1, -1, 0});
seg[i][node].r = seg[i].size() - 1;
}
update(mid + 1, ed, idx, val, i, seg[i][node].r);
}
seg[i][node].val = 0;
if(seg[i][node].l != -1) seg[i][node].val += seg[i][seg[i][node].l].val;
if(seg[i][node].r != -1) seg[i][node].val += seg[i][seg[i][node].r].val;
}
ll query(int str, int ed, int left, int right, int i, int node) {
if(node == -1) return 0;
if(str > right || ed < left) return 0;
if(left <= str && ed <= right) return seg[i][node].val;
int mid = str + ed >> 1;
return query(str, mid, left, right, i, seg[i][node].l) + query(mid + 1, ed, left, right, i, seg[i][node].r);
}
} seg;
vector<pll> H[100005];
vector<ll> dp1[100005], dp2[100005];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
for(int i = 0; i < N; ++i) H[i].push_back({N, 0});
for(int i = 0; i < M; ++i) H[X[i]].push_back({Y[i], W[i]});
for(int i = 0; i < N; ++i) {
seg1.seg[i].push_back({-1, -1, -INF});
seg2.seg[i].push_back({-1, -1, -INF});
seg3.seg[i].push_back({-1, -1, -INF});
seg.seg[i].push_back({-1, -1, 0});
}
for(int i = 0; i < N; ++i) dp1[i].resize(H[i].size(), -INF), dp2[i].resize(H[i].size());
for(int i = 0; i < N; ++i) for(auto j : H[i]) seg.update(0, N, j.first, j.second, i, 0);
auto update = [&](int i) -> void {
for(int j = 0; j < (int)H[i].size(); ++j) {
seg1.update(0, N, H[i][j].first, dp1[i][j] - seg.query(0, N, 0, H[i][j].first - 1, i, 0), i, 0);
seg2.update(0, N, H[i][j].first, dp2[i][j], i, 0);
seg3.update(0, N, H[i][j].first, dp2[i][j] + seg.query(0, N, 0, H[i][j].first - 1, i + 1, 0), i, 0);
}
};
for(int j = 0; j < (int)H[0].size(); ++j) dp1[0][j] = dp2[0][j] = 0;
for(int i = 1; i < N; ++i) {
update(i - 1);
for(int j = 0; j < (int)H[i].size(); ++j) {
dp1[i][j] = max(dp1[i][j], seg.query(0, N, 0, H[i][j].first - 1, i - 1, 0) + seg1.query(0, N, 0, H[i][j].first, i - 1, 0));
if(i >= 2) dp1[i][j] = max(dp1[i][j], seg.query(0, N, 0, H[i][j].first - 1, i - 1, 0) + seg2.query(0, N, 0, H[i][j].first, i - 2, 0));
if(i >= 2) dp1[i][j] = max(dp1[i][j], seg3.query(0, N, H[i][j].first, N, i - 2, 0));
dp2[i][j] = dp1[i][j];
dp2[i][j] = max(dp2[i][j], seg3.query(0, N, H[i][j].first, N, i - 1, 0) - seg.query(0, N, 0, H[i][j].first - 1, i, 0));
}
}
ll ret = 0;
for(int i = 0; i < H[N - 1].size(); ++i) ret = max(ret, dp2[N - 1][i]);
return ret;
}
