#include "fish.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
vector<pair<int, long long> > cs[100010];
long long columnSum(int i, int R) {
if(R < 0) return 0;
if(cs[i].empty()) return 0;
int lb = 0, rb = cs[i].size() - 1;
while(lb < rb) {
int mid = (lb + rb + 1) >> 1;
if(cs[i][mid].first <= R) lb = mid;
else rb = mid - 1;
}
if(cs[i][lb].first <= R) return cs[i][lb].second;
else return 0;
}
vector<int> possible_heights[100010];
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<M; i++) {
cs[X[i]].push_back({Y[i], W[i]});
possible_heights[X[i]].push_back(Y[i]);
}
for(int i=0; i<N; i++) {
possible_heights[i].push_back(0);
possible_heights[i].push_back(N);
}
for(int i=0; i<N; i++) {
sort(possible_heights[i].begin(), possible_heights[i].end());
}
for(int i=0; i<N; i++) sort(cs[i].begin(), cs[i].end());
for(int i=0; i<N; i++) {
for(int j=1; j<cs[i].size(); j++) {
cs[i][j].second += cs[i][j-1].second;
}
}
unordered_map<int, long long> DP[N][2];//0-> upwards, 1->downwards or plains
for(int i=1; i<N; i++) {
// State = 0: upwards (H[i-1] < H[i])
{
// H[i-1] > 0
long long ptr = -1, qq = -5e14;
for(int x: possible_heights[i]) {
while(ptr + 1 < possible_heights[i-1].size() && possible_heights[i-1][ptr + 1] < x) {
ptr++;
int hh = possible_heights[i-1][ptr];
if(hh > 0 || i == 1) qq = max(qq, DP[i-1][0][hh] - columnSum(i-1, hh-1)); // If i = 1, hh = 0 is ok
}
DP[i][0][x] = max(DP[i][0][x], qq + columnSum(i-1, x-1));
}
// H[i-1] = 0
if(i > 1) {
// y 0 x, y < x
ptr = -1, qq = -5e14;
for(int x: possible_heights[i]) {
while(ptr + 1 < possible_heights[i-2].size() && possible_heights[i-2][ptr + 1] < x) {
ptr++;
int hh = possible_heights[i-2][ptr];
long long vv = max(DP[i-2][0][hh], DP[i-2][1][hh]);
qq = max(qq, vv);
}
DP[i][0][x] = max(DP[i][0][x], qq + columnSum(i-1, x-1));
}
// y 0 x, y >= x
ptr = possible_heights[i-2].size(), qq = -5e14;
reverse(possible_heights[i].begin(), possible_heights[i].end());
for(int x: possible_heights[i]) {
while(ptr - 1 >= 0 && possible_heights[i-2][ptr - 1] >= x) {
ptr--;
int hh = possible_heights[i-2][ptr];
long long vv = max(DP[i-2][0][hh], DP[i-2][1][hh]);
qq = max(qq, vv + columnSum(i-1, hh-1));
}
DP[i][0][x] = max(DP[i][0][x], qq);
}
reverse(possible_heights[i].begin(), possible_heights[i].end());
}
}
// State = 1: downwards (H[i-1] >= H[i])
{
reverse(possible_heights[i].begin(), possible_heights[i].end());
long long ptr = possible_heights[i-1].size(), qq = -5e14;
for(int x: possible_heights[i]) {
while(ptr - 1 >= 0 && possible_heights[i-1][ptr - 1] >= x) {
ptr--;
int hh = possible_heights[i-1][ptr];
qq = max(qq, max(DP[i-1][0][hh], DP[i-1][1][hh]) + columnSum(i, hh-1));
}
DP[i][1][x] = max(DP[i][1][x], qq - columnSum(i, x-1));
}
reverse(possible_heights[i].begin(), possible_heights[i].end());
}
for(int x: possible_heights[i]) {
DP[i][0][x] = max(DP[i][0][x], 0ll);
DP[i][1][x] = max(DP[i][1][x], 0ll);
}
}
long long ans = 0;
for(int x: possible_heights[N-1]) ans = max(ans, max(DP[N-1][0][x], DP[N-1][1][x]));
return ans;
}
