#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<pair<int, int>> pos[100100];
struct DP {
ll in, de;
DP() {
in = de = 0;
}
} dp[1001000];
bool ___[100100];
int w[1001000];
int n, m;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N, m = M;
for (int i = 0;i < m;i++) {
w[i + 1] = W[i];
pos[X[i] + 1].push_back({ Y[i] + 1, i + 1 });
if (Y[i] + 1 == 1) ___[X[i] + 1] = 1;
}
int idx = m, p;
ll mx, sum;
for (int i = 2;i <= n;i++) {
if (!___[i]) pos[i].push_back({ 1, ++idx });
pos[i].push_back({ n + 1, ++idx });
sort(pos[i].begin(), pos[i].end());
// h[i-1] < h[i]
{
p = 0;
mx = 0;
for (int j = 0;j < (int)pos[i].size();j++) {
while (p < (int)pos[i - 1].size() && pos[i - 1][p].first <= pos[i][j].first - 1) {
int prev = pos[i - 1][p++].second;
mx = max(mx, dp[prev].in) + w[prev];
}
dp[pos[i][j].second].in = mx;
}
}
// h[i-1] >= h[i]
{
p = pos[i - 1].size() - 1;
mx = 0;
for (int j = pos[i].size() - 1;j >= 0;j--) {
while (p >= 0 && pos[i - 1][p].first > pos[i][j].first) {
int prev = pos[i - 1][p--].second;
mx = max({ mx, dp[prev].in, dp[prev].de });
}
mx += w[pos[i][j].second];
while (p >= 0 && pos[i - 1][p].first == pos[i][j].first) {
int prev = pos[i - 1][p--].second;
mx = max({ mx, dp[prev].in, dp[prev].de });
}
dp[pos[i][j].second].de = mx;
}
}
// in -> de, de -> in
if (i >= 3) {
// h[i-2] <= h[i]
{
int mid = 0;
p = 0;
mx = 0, sum = 0;
for (int j = 0;j < (int)pos[i].size();j++) {
while (p < (int)pos[i - 2].size() && pos[i - 2][p].first <= pos[i][j].first) {
int prev = pos[i - 2][p++].second;
mx = max({ mx ,dp[prev].in, dp[prev].de });
}
while (mid < (int)pos[i - 1].size() && pos[i - 1][mid].first <= pos[i][j].first - 1) {
sum += w[pos[i - 1][mid++].second];
}
dp[pos[i][j].second].in = max(dp[pos[i][j].second].in, mx + sum);
}
}
// h[i-2] >= h[i]
{
int mid = pos[i - 1].size() - 1;
mx = 0, sum = 0;
for (int j = 0;j <= mid;j++) sum += w[pos[i - 1][j].second];
p = pos[i - 2].size() - 1;
for (int j = pos[i].size() - 1;j >= 0;j--) {
while (p >= 0 && pos[i - 2][p].first >= pos[i][j].first) {
int prev = pos[i - 2][p].second;
int now = pos[i - 2][p].first - 1;
while (mid >= 0 && pos[i - 1][mid].first > now) {
sum -= w[pos[i - 1][mid--].second];
}
mx = max({ mx, dp[prev].in + sum, dp[prev].de + sum });
p--;
}
dp[pos[i][j].second].in = max(dp[pos[i][j].second].in, mx);
}
}
}
}
ll ans = 0;
for (int i = 1;i <= idx;i++) {
ans = max(ans, dp[i].in);
ans = max(ans, dp[i].de);
}
return ans;
}
