#include "fish.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
using namespace std;
const int N_MAX = 1e5 + 11;
const int INC = 0;
const int DEC = 1;
const int ZERO = 2;
vector<pair<int, long long>> fish[N_MAX];
int N;
void chmax(long long& x, long long y){
x = max(x, y);
}
long long g(int x, int y){ // [x, x] times [0, y)
if(x <= 0 || x > N) return 0;
auto ptr = lower_bound(fish[x].begin(), fish[x].end(), pair<int, long long>{y, -1LL});
if(ptr == fish[x].begin()) return 0;
return (--ptr)->se;
}
vector<long long> dp[N_MAX][3];
vector<int> sp[N_MAX];
int L[N_MAX];
int at(int x, int y){
if(0 <= y && y < sp[x].size())
return sp[x][y];
assert(0 == 1);
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
::N = N;
for(int i = 0; i < M; i++) X[i]++;
for(int i = 0; i < M; i++){
fish[X[i]].push_back({Y[i], W[i]});
}
for(int i = 1; i <= N; i++){
sort(fish[i].begin(), fish[i].end());
for(int j = 1; j < fish[i].size(); j++){
fish[i][j].se += fish[i][j - 1].se;
}
}
for(int i = 0; i < M; i++){
int x = X[i], y = Y[i];
if(x > 1) sp[x - 1].push_back(y + 1);
if(x < N) sp[x + 1].push_back(y + 1);
}
for(int i = 0; i <= N; i++){
sp[i].push_back(0);
for(int j = 0; j < 10; j++){
sp[i].push_back(j);
}
sort(sp[i].begin(), sp[i].end());
sp[i].resize(unique(sp[i].begin(), sp[i].end()) - sp[i].begin());
for(int j = 0; j < 3; j++){
dp[i][j].resize(sp[i].size());
fill(all(dp[i][j]), -1E18);
}
L[i] = sp[i].size();
}
dp[0][ZERO][0] = 0;
for(int x = 1; x <= N; x++){
/*
for(int y = 0; y <= N; y++){
chmax(dp[ZERO][x + 1][y], dp[INC][x][y]);
chmax(dp[ZERO][x + 1][y], dp[DEC][x][y]);
chmax(dp[ZERO][x + 1][0], dp[ZERO][x][y]);
}
for(int y = 0; y < N; y++){
chmax(dp[ZERO][x + 1][y + 1], dp[ZERO][x + 1][y]);
}
*/
// ZERO
{
for(int y = 0; y < L[x - 1]; y++){
chmax(dp[x][ZERO][0], dp[x - 1][ZERO][y]);
}
int y1 = 0;
for(int y2 = 0; y2 < L[x]; y2++){
while (y1 < L[x - 1] && at(x - 1, y1) <= at(x, y2)) {
chmax(dp[x][ZERO][y2], dp[x - 1][INC][y1]);
chmax(dp[x][ZERO][y2], dp[x - 1][DEC][y1]);
y1++;
}
}
for(int y = 0; y < L[x] - 1; y++){
chmax(dp[x][ZERO][y + 1], dp[x][ZERO][y]);
}
}
long long value = -(1LL << 60);
/*
for(int y2 = 0; y2 <= N; y2++){
value = max(value, dp[INC][x][y2] - g(x, y2) - g(x - 1, y2));
chmax(dp[INC][x + 1][y2], value + g(x + 1, y2) + g(x - 1, y2));
}
value = -(1LL << 60);
for(int y2 = 0; y2 <= N; y2++){
chmax(value, dp[ZERO][x][y2] - g(x - 1, y2));
chmax(dp[INC][x + 1][y2], dp[ZERO][x][y2] + g(x + 1, y2));
chmax(dp[INC][x + 1][y2], value + g(x + 1, y2) + g(x - 1, y2));
}
*/
// INC
{
int y1 = 0;
for(int y2 = 0; y2 < L[x]; y2++){
while (y1 < L[x - 1] && at(x - 1, y1) <= at(x, y2)) {
chmax(value, dp[x - 1][INC][y1] - g(x, at(x - 1, y1)) - g(x - 1, at(x - 1, y1)));
y1++;
}
chmax(dp[x][INC][y2], value + g(x + 1, at(x, y2)) + g(x - 1, at(x, y2)));
}
value = -(1LL << 60);
y1 = 0;
for(int y2 = 0; y2 < L[x]; y2++){
while (y1 < L[x - 1] && at(x - 1, y1) <= at(x, y2)) {
chmax(value, dp[x - 1][ZERO][y1] - g(x - 1, at(x - 1, y1)));
y1++;
}
chmax(dp[x][INC][y2], dp[x - 1][ZERO][L[x - 1] - 1] + g(x + 1, at(x, y2)));
chmax(dp[x][INC][y2], value + g(x + 1, at(x, y2)) + g(x - 1, at(x, y2)));
}
}
/*
for(int y2 = N; y2 >= 0; y2--){
chmax(value, dp[DEC][x][y2]); chmax(value, dp[INC][x][y2]);
chmax(dp[DEC][x + 1][y2], value + g(x + 1, y2) - g(x, y2));
}
*/
// DEC
{
value = -(1LL << 60);
int y1 = L[x - 1] - 1;
for(int y2 = L[x] - 1; y2 >= 0; y2--){
while (y1 >= 0 && at(x - 1, y1) >= at(x, y2)) {
chmax(value, dp[x - 1][DEC][y1]); chmax(value, dp[x - 1][INC][y1]);
y1--;
}
chmax(dp[x][DEC][y2], value + g(x + 1, at(x, y2)) - g(x, at(x, y2)));
}
}
}
long long ans = 0;
/*
for(int i = 0; i <= N; i++){
for(int k = 0; k < 3; k++){
for(int j = 0; j < L[i]; j++){
cout << dp[i][k][j] << ' ';
}
cout << endl;
}
cout << endl;
}
*/
for(int k = 0; k < 3; k++){
for(int y = 0; y < L[N]; y++){
ans = max(ans, dp[N][k][y]);
}
}
return ans;
}
