#include "fish.h"
#include <bits/stdc++.h>
#define uwu return
using namespace std;
#define fs first
#define sc second
#define all(x) x.begin(), x.end()
const int SIZE = 1e5 + 5;
vector <int> valid_state[SIZE];
vector <pair<int, int>> fishes[SIZE];
vector <long long> dp[SIZE][2];
void chmax(long long &a, long long b){
a = max(a, b);
uwu;
}
void output(long long a, bool b){
if(b)
cerr << '\n';
else
cerr << a << ' ';
return;
}
const long long INF = 1e18 + 7;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int i = 0; i < N; i++){
valid_state[i].push_back(-1);
valid_state[i].push_back(N - 1);
}
for (int i = 0; i < M; i++){
if(X[i] != 0)
valid_state[X[i] - 1].push_back(Y[i]);
if(X[i] != N - 1)
valid_state[X[i] + 1].push_back(Y[i]);
fishes[X[i]].push_back({Y[i], W[i]});
}
for (int i = 0; i < N; i++){
sort(all(valid_state[i]));
sort(all(fishes[i]));
for (auto j : valid_state[i]){
dp[i][0].push_back(0);
dp[i][1].push_back(0);
}
}
for (int i = 1; i < N; i++){
int nst_a = valid_state[i].size(), pst_a = valid_state[i - 1].size(), nfs_a = fishes[i].size(), pfs_a = fishes[i - 1].size();
vector <long long> pp_pref, np_pref, pn_pref, nn_pref;
// pp, np prefix of the previous fishes, pn, nn prefix of this round's fishes
for (long long ptr = 0, sum = 0, j = 0; j < pst_a; j++){
while(ptr < pfs_a && fishes[i - 1][ptr].fs <= valid_state[i - 1][j]){
sum += fishes[i - 1][ptr].sc;
ptr++;
}
pp_pref.push_back(sum);
}
for (long long ptr = 0, sum = 0, j = 0; j < nst_a; j++){
while(ptr < pfs_a && fishes[i - 1][ptr].fs <= valid_state[i][j]){
sum += fishes[i - 1][ptr].sc;
ptr++;
}
np_pref.push_back(sum);
}
for (long long ptr = 0, sum = 0, j = 0; j < pst_a; j++){
while(ptr < nfs_a && fishes[i][ptr].fs <= valid_state[i - 1][j]){
sum += fishes[i][ptr].sc;
ptr++;
}
pn_pref.push_back(sum);
}
for (long long ptr = 0, sum = 0, j = 0; j < nst_a; j++){
while(ptr < nfs_a && fishes[i][ptr].fs <= valid_state[i][j]){
sum += fishes[i][ptr].sc;
ptr++;
}
nn_pref.push_back(sum);
}
for(auto j:dp[i - 1][1]){
chmax(dp[i][0][0], j);
}
for (int j = 1; j < nst_a; j++){
dp[i][0][j] = dp[i][0][0];
}
for (long long ptr = 0, mx = -INF, j = 0; j < nst_a; j++){
while(ptr < pst_a && valid_state[i - 1][ptr] <= valid_state[i][j]){
chmax(mx, dp[i - 1][0][ptr] - pp_pref[ptr]);
ptr++;
}
chmax(dp[i][0][j], mx + np_pref[j]);
}
for (int j = 0; j < nst_a; j++){
chmax(dp[i][1][j], dp[i][0][j]);
}
for (long long ptr = pst_a - 1, mx = -INF, j = nst_a - 1; j >= 0; j--){
while(ptr >= 0 && valid_state[i - 1][ptr] >= valid_state[i][j]){
chmax(mx, dp[i - 1][1][ptr] + pn_pref[ptr]);
ptr--;
}
chmax(dp[i][1][j], mx - nn_pref[j]);
}
}
// for (int i = 0; i < N; i++){
// for (int j = 0; j < (int)valid_state[i].size(); j++){
// output(i, 0);
// output(valid_state[i][j], 0);
// output(dp[i][0][j], 0);
// output(dp[i][1][j], 0);
// output(0, 1);
// }
// }
long long ans = 0;
for(auto i:dp[N - 1][0]){
chmax(ans, i);
}
for(auto i:dp[N - 1][1]){
chmax(ans, i);
}
return ans;
}
