#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL << 60);
struct value{
int y; long long ans;
};
struct catfish{
int y, w; long long s;
bool operator< (const catfish& o) const {
return y < o.y;
}
};
const int MAXN = 1e5 + 11;
vector<value> DP[3][MAXN];
vector<catfish> F[MAXN];
int S[MAXN];
long long prefix_weight(int x, int y){
int idx = upper_bound(F[x].begin(), F[x].end(), catfish{y}) - F[x].begin() - 1;
return F[x][idx].s;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for(int i = 0; i < M; i++) X[i]++;
for(int i = 0; i <= N + 1; i++){
F[i].push_back({-1, 0});
}
for(int i = 0; i < M; i++){
F[X[i]].push_back({Y[i], W[i]});
}
for(int i = 1; i <= N; i++){
sort(F[i].begin(), F[i].end());
for(int j = 1; j < (int) F[i].size(); j++){
F[i][j].s = F[i][j - 1].s + F[i][j].w;
}
}
for(int i = 1; i <= N; i++){
vector<int> sp {-1};
for(auto [y, w, s] : F[i - 1]) sp.push_back(y);
for(auto [y, w, s] : F[i]) sp.push_back(y);
for(auto [y, w, s] : F[i + 1]) sp.push_back(y);
sort(sp.begin(), sp.end()); sp.resize(unique(sp.begin(), sp.end()) - sp.begin());
for(auto v : sp) DP[0][i].push_back({v, 0}), DP[1][i].push_back({v, 0}), DP[2][i].push_back({v, 0}); S[i] = sp.size();
}
for(int x = 1; x <= N; x++){
int pd0 = 0, pd1 = 0, pd2 = 0;
// 0 to 0
pd0 = 0; long long dp_max = 0;
for(auto& [h, ans] : DP[0][x]){
while(pd0 < S[x - 1] && DP[0][x - 1][pd0].y <= h) dp_max = max(dp_max, DP[0][x - 1][pd0].ans - prefix_weight(x - 1, DP[0][x - 1][pd0].y) - prefix_weight(x, DP[0][x - 1][pd0].y)), pd0++;
ans = max(ans, prefix_weight(x - 1, h) + prefix_weight(x + 1, h) + dp_max);
}
// 2 to 0
pd2 = S[x - 1] - 1; dp_max = -INF;
for(int i = S[x] - 1; i >= 0; i--){
int h = DP[0][x][i].y;
while(pd2 >= 0 && DP[2][x - 1][pd2].y >= h) dp_max = max(dp_max, DP[2][x - 1][pd2--].ans);
DP[0][x][i].ans = max(DP[0][x][i].ans, prefix_weight(x + 1, h) + dp_max);
}
// 2 to 0
pd2 = 0; dp_max = 0;
for(auto& [h, ans] : DP[0][x]){
while(pd2 < S[x - 1] && DP[2][x - 1][pd2].y <= h) dp_max = max(dp_max, DP[2][x - 1][pd2].ans - prefix_weight(x - 1, DP[2][x - 1][pd2].y)), pd2++;
ans = max(ans, prefix_weight(x - 1, h) + prefix_weight(x + 1, h) + dp_max);
}
// 0 and 1 to 1
pd0 = S[x - 1] - 1, pd1 = S[x - 1] - 1; dp_max = -INF;
for(int i = S[x] - 1; i >= 0; i--){
int h = DP[1][x][i].y;
while(pd0 >= 0 && DP[0][x - 1][pd0].y >= h) dp_max = max(dp_max, DP[0][x - 1][pd0--].ans);
while(pd1 >= 0 && DP[1][x - 1][pd1].y >= h) dp_max = max(dp_max, DP[1][x - 1][pd1--].ans);
DP[1][x][i].ans = max(DP[1][x][i].ans, dp_max + prefix_weight(x + 1, h) - prefix_weight(x, h));
}
// 0 and 1 to 2
pd0 = S[x - 1] - 1, pd1 = S[x - 1] - 1;
for(int i = S[x] - 1; i >= 0; i--){
int h = DP[2][x][i].y; dp_max = 0;
while(pd0 >= 0 && DP[0][x - 1][pd0].y >= h) dp_max = max(dp_max, DP[0][x - 1][pd0].ans), pd0--;
while(pd1 >= 0 && DP[1][x - 1][pd1].y >= h) dp_max = max(dp_max, DP[1][x - 1][pd1].ans), pd1--;
DP[2][x][i].ans = max(DP[2][x][i].ans, dp_max);
}
// 2 to 2
dp_max = 0;
for(int i = 0; i < S[x - 1]; i++){
dp_max = max(dp_max, DP[2][x - 1][i].ans);
}
DP[2][x][0].ans = max(DP[2][x][0].ans, dp_max);
}
long long ans = 0;
for(int i = 0; i < 3; i++){
for(int j = 0; j < S[N]; j++){
ans = max(ans, DP[i][N][j].ans);
}
}
return ans;
}
