#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
};
long long 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));
long long largest = 0;
vector<pl> up, down;
vector<vl> dp(M, vl(2, -1e18));
for (int x = 0; x < N; ++x) {
sort(fishes[x].begin(), fishes[x].end());
if (x > 0) {
long long max_down = 0;
for (int j = (int)fishes[x].size() - 1; j >= 0; --j) {
int y = fishes[x][j].first;
int i = fishes[x][j].V;
while (down.size() > 0 && down.back().first > y) {
max_down = max(max_down, down.back().V);
down.pop_back();
}
long long &ret = dp[i][DOWN];
ret = largest + W[i];
ret = max(ret, max_down + W[i]);
if (j + 1 < fishes[x].size()) {
ret = max(ret, dp[fishes[x][j + 1].V][DOWN] + W[i]);
}
}
}
if (x >= 1) {
for (auto [y, i] : fishes[x - 1]) {
largest = max(largest, dp[i][DOWN]);
}
}
long long max_up = 0;
for (int j = 0; j < fishes[x].size(); ++j) {
int y = fishes[x][j].first;
int i = fishes[x][j].V;
while (up.size() > 0 && up.back().first < y) {
max_up = max(max_up, up.back().V);
up.pop_back();
}
long long &ret = dp[i][UP];
ret = largest + W[i];
ret = max(ret, max_up + W[i]);
if (j > 0) {
ret = max(ret, dp[fishes[x][j - 1].V][UP] + W[i]);
}
}
if (x >= 1) {
for (auto [y, i] : fishes[x - 1]) {
largest = max(largest, dp[i][UP]);
}
}
down.clear();
for (int j = 0; j < fishes[x].size(); ++j) {
down.push_back(make_pair(fishes[x][j].first, dp[fishes[x][j].V][DOWN]));
}
up.clear();
for (int j = fishes[x].size() - 1; j >= 0; --j) {
up.push_back(make_pair(fishes[x][j].first, dp[fishes[x][j].V][UP]));
}
}
long long answer = 0;
for (int i = 0; i < M; ++i) {
answer = max(answer, dp[i][DOWN]);
if (X[i] + 1 < N) {
answer = max(answer, dp[i][UP]);
}
}
return answer;
}
