#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<pl>> fishes(N);
F(i, 0, M) fishes[X[i]].push_back(make_pair(Y[i], i));
vector<pl> up, down; // stores [ypos, dpvalue] of prev state
vector<vl> dp(M, vl(2)); // dp[fish index][type]
ll largest = 0; // arbitrary transition to previous state if far back enough??? [idk yet]
F(x, 0, N) {
if (x > 0) {
sort(A(fishes[x]), greater());
ll max_down = 0, prev = 0;
for (auto [y, i]: fishes[x]) {
while (down.size() && down.back().K > y) {
max_down = max(max_down, down.back().V);
down.pop_back();
}
dp[i][DOWN] = max({largest, max_down, prev}) + W[i];
prev = max(prev, dp[i][DOWN]);
}
}
// i don't get why we have to do this here specifically??
if (x >= 1) for (auto [y, i] : fishes[x - 1]) largest = max(largest, dp[i][DOWN]);
if (x + 1 < N) {
sort(A(fishes[x]));
ll max_up = 0, prev = 0;
for (auto [y, i]: fishes[x]) {
while (up.size() && up.back().K < y) {
max_up = max(max_up, up.back().V);
up.pop_back();
}
dp[i][UP] = max({largest, max_up, 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();
sort(A(fishes[x]));
for (auto [y, i]: fishes[x]) down.emplace_back(y, dp[i][DOWN]);
up.clear();
sort(A(fishes[x]), greater());
for (auto [y, i]: fishes[x]) up.emplace_back(y, dp[i][UP]);
}
ll answer = 0;
for (auto &x: dp) answer = max(*max_element(A(x)), answer);
return answer;
}
