#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
enum {
UP = 0,
DOWN = 1
};
ll max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<vector<pair<int, int>>> fishes(N);
F(i, 0, M) fishes[X[i]].push_back(make_pair(Y[i], i));
ll largest = 0;
vector<pl> up, down; // stores [ypos, dpvalue] of prev state
vector<vl> dp(M, vl(2, -1e18)); // dp[fish index][type]
F(x, 0, N) {
// computes dp[down] for layer
if (x > 0) { // w/o this check, we allow placing piers to index -1 which is no bueno
sort(A(fishes[x]), greater());
ll max_down = 0, prev = -1e18;
for (auto [y, i]: fishes[x]) {
while (down.size() > 0 && down.back().K > y) {
max_down = max(max_down, down.back().V);
down.pop_back();
}
ll &ret = dp[i][DOWN];
ret = largest + W[i];
ret = max(ret, max_down + W[i]);
ret = max(ret, prev + W[i]);
prev = max(prev, dp[i][DOWN]);
}
}
if (x >= 1) for (auto [y, i] : fishes[x - 1]) {
largest = max(largest, dp[i][DOWN]);
}
// computes dp[up] for layer; ig implciitly we can already think about largest as the previous dpdown???
{
sort(A(fishes[x]));
ll max_up = 0, prev = -1e18;
for (auto [y, i]: fishes[x]) {
while (up.size() > 0 && up.back().K < y) {
max_up = max(max_up, up.back().V);
up.pop_back();
}
ll &ret = dp[i][UP];
ret = largest + W[i];
ret = max(ret, max_up + W[i]);
ret = max(ret, prev + W[i]);
prev = max(prev, dp[i][UP]);
}
}
if (x >= 1) for (auto [y, i] : fishes[x - 1]) {
largest = max(largest, dp[i][UP]);
}
down.clear();
for (auto [y, i]: fishes[x]) down.emplace_back(y, dp[i][DOWN]);
up.clear();
for (auto [y, i]: fishes[x]) up.emplace_back(y, dp[i][UP]);
reverse(A(up));
}
ll answer = 0;
F(i, 0, M) {
answer = max(answer, dp[i][DOWN]);
if (X[i] + 1 < N) answer = max(answer, dp[i][UP]);
}
return answer;
}
