#include "fish.h"
#include <vector>
#include <algorithm>
#include <iostream>
#define int long long
using namespace std;
vector<pair<int, int>> adj[100005];
vector<pair<int, int>> prf[100005];
const long long inf = 1e18;
int _N;
int get_prfsum(int X, int to)
{
if (X <= 0 || _N+1 <= X) return 0;
return (*--lower_bound(prf[X].begin(), prf[X].end(), make_pair(to, inf))).second;
}
vector<int> dp[100005][3];
vector<int> suf[100005];
vector<int> prf0[100005], prf1[100005], suf0[100005];
vector<int> cpx[100005];
long long max_weights(signed N, signed M, std::vector<signed> X, std::vector<signed> Y,
std::vector<signed> W) {
_N= N;
for (int i = 0; i < M; i++) {
adj[X[i]+1].push_back(make_pair(Y[i] + 2, W[i]));
}
for (int i = 1; i <= N; i++) sort(adj[i].begin(), adj[i].end());
for (int i = 1; i <= N; i++) {
prf[i].resize(adj[i].size() + 1);
prf[i][0] = make_pair(0, 0);
for (int k = 1; k <= adj[i].size(); k++) {
prf[i][k] = make_pair(adj[i][k-1].first, adj[i][k-1].second + prf[i][k-1].second);
}
}
cpx[0].push_back(0);
for (int i = 1; i <= N; i++) {
cpx[i].push_back(0);
for (pair<int, int> p:adj[i]) cpx[i].push_back(p.first - 1);
cpx[i].push_back(N+1);
}
for (int i = 1; i <= N; i++) {
dp[i][0].resize(cpx[i].size());
dp[i][1].resize(cpx[i].size());
dp[i][2].resize(cpx[i-1].size());
suf[i].resize(dp[i][0].size());
prf0[i].resize(dp[i][0].size());
prf1[i].resize(dp[i][2].size());
suf0[i].resize(dp[i][2].size());
}
for (int i = 1; i <= N; i++) {
if (i >= 2) {
for (int j = 0; j < (int)dp[i-1][2].size(); j++) dp[i][2][0] = max(dp[i][2][0], dp[i-1][2][j]);
for (int j = 1; j < (int)dp[i][2].size(); j++) {
dp[i][2][j] = max(dp[i-1][0][j], dp[i-1][1][j]) + get_prfsum(i, cpx[i-1][j]);
}
for (int j = 1; j < (int)dp[i][1].size(); j++) {
int height = cpx[i][j]; //height까지 끌어올리기
//height보다 더 '큰' 최초의 인덱스 k를 찾자
int low = upper_bound(cpx[i-1].begin(), cpx[i-1].end(), height) - cpx[i-1].begin();
if (low == cpx[i-1].size()) {
dp[i][1][j] = -inf;
continue;
}
dp[i][1][j] = suf[i-1][low] - get_prfsum(i, cpx[i][j]);
}
for (int j = 1; j < (int)dp[i][0].size(); j++) {
int ord = upper_bound(cpx[i-1].begin(), cpx[i-1].end(), cpx[i][j]) - cpx[i-1].begin();
int M1 = ord == 1 ? -inf : (prf0[i-1][ord-1] + get_prfsum(i-1, cpx[i][j]));
int ord2 = upper_bound(cpx[i-2].begin(), cpx[i-2].end(), cpx[i][j]) - cpx[i-2].begin();
int M2 = prf1[i-1][ord2-1] + get_prfsum(i-1, cpx[i][j]);
int M3 = (i == 2 || ord2 >= cpx[i-2].size()) ? -inf : suf0[i-1][ord2];
dp[i][0][j] = max({M1, M2, M3});
}
}
for (int j = 1; j < (int)dp[i][1].size(); j++) {
prf0[i][j] = dp[i][0][j] - get_prfsum(i, cpx[i][j]);
suf[i][j] = max(dp[i][0][j], dp[i][1][j]) + get_prfsum(i+1, cpx[i][j]);
}
for (int j = 0; j < (int)dp[i][2].size(); j++) {
prf1[i][j] = dp[i][2][j] - get_prfsum(i, cpx[i-1][j]);
suf0[i][j] = dp[i][2][j];
}
for (int j = 2; j < (int)dp[i][1].size(); j++) prf0[i][j] = max(prf0[i][j], prf0[i][j-1]);
for (int j = 1; j < (int)dp[i][2].size(); j++) prf1[i][j] = max(prf1[i][j], prf1[i][j-1]);
for (int j = (int)dp[i][2].size() - 2; j >= 0; j--) suf0[i][j] = max(suf0[i][j], suf0[i][j+1]);
for (int j = (int)dp[i][1].size() - 2; j >= 1; j--) suf[i][j] = max(suf[i][j], suf[i][j+1]);
}
int ans = 0;
for (int i = 1; i < (int)dp[N][0].size(); i++) {
ans = max(ans, dp[N][0][i]);
}
for (int i = 1; i < (int)dp[N][1].size(); i++) ans = max(ans, dp[N][1][i]);
for (int i = 0; i < (int)dp[N][2].size(); i++) ans = max(ans, dp[N][2][i]);
return ans;
}
