#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define mp make_pair
using ll = long long;
using ii = pair<int, int>;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
auto tmp = vector<ll>(N + M), tmp2 = vector<ll>(N + M);
auto dp = vector<vector<ll> >(N + M, vector<ll>(4, 0));
auto col = vector<vector<ii> >(N);
for (int i = 0; i < M; i++) {
col[X[i]].eb(Y[i], i);
}
for (int i = 0; i < N; i++) {
sort(col[i].begin(), col[i].end());
}
for (int i = 0; i <= N; i++) {
{
// ty == 0
if (i > 0) {
dp[i][0] = max({0ll, dp[i - 1][0], dp[i - 1][1]});
} else {
dp[i][0] = 0;
}
if (i && !col[i - 1].empty()) {
dp[i][0] = max(dp[i][0], dp[col[i - 1][0].second][2]);
}
}
{
// ty == 1
if (i > 0) {
dp[i][1] = max({0ll, dp[i - 1][0], dp[i - 1][1]});
} else {
dp[i][1] = 0;
}
if (i && !col[i - 1].empty()) {
dp[i][1] = max(dp[i][1], dp[col[i - 1][0].second][2]);
dp[i][1] = max(dp[i][1], dp[col[i - 1].back().second][3]);
}
}
if (i < N) {
// ty == 2
{
ll sum_all = 0;
for (int _ = (int)col[i].size() - 1; _ >= 0; _--) {
int p = col[i][_].second, x = X[p];
sum_all += W[p];
if (x - 1 >= 0) {
dp[p][2] = max(dp[p][2], dp[x - 1][1] + sum_all);
}
}
if (i && !col[i - 1].empty()) {
int ptr = 0;
ll pf_sum = 0;
for (int _ = 0; _ < (int)col[i - 1].size(); _++) {
while (ptr < (int)col[i].size() && col[i - 1][_].first > col[i][ptr].first) {
pf_sum += W[col[i][ptr].second];
ptr++;
}
tmp[_] = pf_sum;
}
pf_sum = 0;
for (int _ = 0; _ < (int)col[i].size(); _++) {
tmp2[_] = pf_sum;
pf_sum += W[col[i][_].second];
}
ptr = (int)col[i - 1].size() - 1;
ll rs = -(ll)1e16;
for (int _ = (int)col[i].size() - 1; _ >= 0; _--) {
while (ptr >= 0 && col[i - 1][ptr].first > col[i][_].first) {
rs = max(rs, dp[col[i - 1][ptr].second][2] + tmp[ptr]);
ptr--;
}
dp[col[i][_].second][2] = max(dp[col[i][_].second][2], rs - tmp2[_]);
}
}
}
// ty == 3
{
ll sum_all = 0;
for (int _ = 0; _ < (int)col[i].size(); _++) {
int p = col[i][_].second, x = X[p];
sum_all += W[p];
dp[p][3] = max(dp[p][3], dp[x][0] + sum_all);
}
if (i && !col[i - 1].empty()) {
int ptr = (int)col[i].size() - 1;
ll pf_sum = 0;
for (int _ = (int)col[i - 1].size() - 1; _ >= 0; _--) {
while (ptr >= 0 && col[i - 1][_].first < col[i][ptr].first) {
pf_sum += W[col[i][ptr].second];
ptr--;
}
tmp[_] = pf_sum;
}
pf_sum = 0;
for (int _ = (int)col[i].size() - 1; _ >= 0; _--) {
tmp2[_] = pf_sum;
pf_sum += W[col[i][_].second];
}
ptr = 0;
ll rs = -(ll)1e16;
for (int _ = 0; _ < (int)col[i].size(); _++) {
while (ptr < (int)col[i - 1].size() && col[i - 1][ptr].first < col[i][_].first) {
rs = max(rs, dp[col[i - 1][ptr].second][3] + tmp[ptr]);
ptr++;
}
dp[col[i][_].second][3] = max(dp[col[i][_].second][3], rs - tmp2[_]);
}
}
}
}
}
return dp[N][0];
}
