#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector <pair<ll, ll>> points[N+5];
for (int i = 0; i < M; i++) {
X[i]++, Y[i]++;
points[X[i]].push_back({Y[i], W[i]});
points[X[i]].push_back({Y[i]-1, 0});
if (X[i]+1 <= N) {
points[X[i]+1].push_back({Y[i], 0});
points[X[i]+1].push_back({Y[i], 0});
}
}
for (int i = 0; i <= N; i++) {
points[i].push_back({0, 0});
}
for (int i = 1; i <= N; i++) {
sort(points[i].begin(), points[i].end());
// compress these points
vector <pair<ll, ll>> tmp;
for (auto [x, y] : points[i]) {
if (!tmp.size()) tmp.push_back({x, y});
else if (tmp.back().first == x) tmp.back().second += y;
else tmp.push_back({x, y});
}
points[i].swap(tmp);
}
vector <vector<vector<ll>>> dp(N+5, vector <vector<ll>> (2));
vector <vector<ll>> ps(N+5), sf(N+5);
vector <ll> MX(N+5, -INF);
for (int i = 0; i <= N; i++) {
dp[i][0].resize(points[i].size()+1, -INF), dp[i][1].resize(points[i].size()+1, -INF);
ps[i].resize(points[i].size()+1, -INF), sf[i].resize(points[i].size()+1, -INF);
for (int j = 1; j < (ll)points[i].size(); j++) {
points[i][j].second += points[i][j-1].second;
}
}
dp[0][0][0] = 0;
ll ans = 0;
for (int i = 0; i <= N; i++) {
if (i) {
for (int j = 0; j < (ll)points[i-1].size(); j++) {
dp[i][0][0] = max(dp[i][0][0], dp[i-1][0][j]);
dp[i][0][0] = max(dp[i][0][0], dp[i-1][1][j]);
}
for (int j = 1; j < (ll)points[i].size(); j++) {
if (i < N) {
// increasing
dp[i][0][j] = max(dp[i][0][j], ps[i][j-1] + points[i][j].second);
dp[i][0][j] = max(dp[i][0][j], MX[i-1] + points[i][j].second);
}
if (i > 1) {
// decreasing
dp[i][1][j] = max(dp[i][1][j], sf[i][j+1] - points[i][j-1].second);
dp[i][1][j] = max(dp[i][1][j], dp[i-1][0][0] + (points[i].back().second-points[i][j-1].second));
}
ans = max({ans, dp[i][0][j], dp[i][1][j]});
MX[i] = max(MX[i], dp[i][1][j]);
}
}
if (i+1 <= N) {
ps[i+1][0] = dp[i][0][0];
ll ptr = 0;
for (int j = 1; j < (ll)points[i+1].size(); j++) {
ps[i+1][j] = ps[i+1][j-1];
while (ptr < (ll)points[i].size() && points[i][ptr].first < points[i+1][j].first) ptr++;
if (ptr < points[i].size() && points[i][ptr].first == points[i+1][j].first) {
ps[i+1][j] = max(ps[i+1][j], dp[i][0][ptr] - points[i+1][j].second);
}
}
ptr = points[i].size()-1;
for (int j = points[i+1].size()-1; j >= 0; --j) {
sf[i+1][j] = sf[i+1][j+1];
while (ptr >= 0 && points[i][ptr].first > points[i+1][j].first) ptr--;
if (ptr >= 0 && points[i][ptr].first == points[i+1][j].first) {
sf[i+1][j] = max(sf[i+1][j], dp[i][1][ptr] + (j == 0 ? 0LL : points[i+1][j-1].second));
}
}
}
}
return ans;
}
