#include <bits/stdc++.h>
#include "fish.h"

using namespace std;
typedef long long i64; 

int x[300005], y[300005], w[300005]; 
i64 dp[300005][2], f[300005], g[300005]; // [][0] 代表上升
// f g 分别代表现在是增、减的最优值
vector<int> v[300005]; // i 位置上的垒球
i64 max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
    for (int i = 0; i < m; ++i) {
        x[i + 1] = X[i] + 1, y[i + 1] = Y[i] + 1, w[i + 1] = W[i];
        v[X[i] + 1].emplace_back(i + 1);
    }

    for (int i = 1; i <= n; ++i) {
        sort(v[i].begin(), v[i].end(), [&](int a, int b) { return y[a] < y[b]; });
        f[i] = g[i] = max(f[i - 1], g[i - 1]);

        int l1 = v[i - 1].size(), l2 = v[i].size(), c = l1; 
        i64 mx = i >= 2 ? max(f[i - 2], g[i - 2]) : 0;

        if (i != 1) {
            for (int j = l2 - 1; j >= 0; --j) {
                if (j < l2 - 1) dp[v[i][j]][0] = dp[v[i][j + 1]][0] + w[v[i][j]];
                while (c && y[v[i - 1][c - 1]] > y[v[i][j]])
                    mx = max(mx, dp[v[i - 1][--c]][0]);
                dp[v[i][j]][0] = max(dp[v[i][j]][0], mx + w[v[i][j]]); 
                f[i] = max(f[i], dp[v[i][j]][0]);
            }
        }

        c = 0; mx = f[i - 1];
        if (i != n) {
            for (int j = 0; j < l2; ++j) {
                if (j) dp[v[i][j]][1] = dp[v[i][j - 1]][1] + w[v[i][j]];
                while (c < l1 && y[dp[i - 1][c]] < y[dp[i][j]])
                    mx = max(mx, dp[v[i - 1][c++]][1]);
                dp[v[i][j]][1] = max(dp[v[i][j]][1], mx + w[v[i][j]]); 
                g[i] = max(g[i], dp[v[i][j]][1]);
            }
        }
    }
    i64 ans = 0;
    for (int i = 1; i <= m; ++i) ans = max({ans, dp[i][0], dp[i][1]});
    return ans;
}