#include "fish.h"

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>

long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    std::vector<std::vector<std::pair<int, int>>> input(n);
    for (int i = 0; i < m; i++) {
        input[X[i]].push_back({Y[i], W[i]});
    }

    std::vector<std::vector<int>> bd(n);
    std::vector<std::vector<int64_t>> prf(n);
    std::vector<std::vector<int64_t>> prf2(n);
    std::vector<std::vector<int64_t>> prf3(n);

    auto lb = [&](int i, int val) {
        int it = std::lower_bound(input[i].begin(), input[i].end(), std::pair<int, int>{val, -1}) - input[i].begin();
        return it;
    };
    auto get_cum = [&](int i, int l, int r) {
        int64_t res = prf[i][lb(i, r)] - prf[i][lb(i, l)];
        return res;
    };

    for (int i = 0; i < n; i++) {
        std::sort(input[i].begin(), input[i].end());

        bd[i].resize(input[i].size() + 1);
        for (int j = 0; j < input[i].size(); j++) {
            bd[i][j] = input[i][j].first;
        }
        bd[i].back() = n + 1;

        prf[i].resize(input[i].size() + 1);
        for (int j = 0; j < input[i].size(); j++) {
            prf[i][j + 1] = prf[i][j] + input[i][j].second;
        }
    }
    for (int i = 0; i < n - 1; i++) {
        prf2[i].resize(input[i].size() + 1);
        for (int j = 0; j <= input[i].size(); j++) {
            int it = lb(i + 1, bd[i][j]);
            prf2[i][j] = prf[i + 1][it];
        }
    }
    for (int i = 1; i < n; i++) {
        prf3[i].resize(input[i].size() + 1);
        for (int j = 0; j <= input[i].size(); j++) {
            int it = lb(i - 1, bd[i][j]);
            prf3[i][j] = prf[i - 1][it];
        }
    }
    if (input[0].size() + input[1].size() == m) {
        if (n == 2) {
            return std::max(prf[0].back(), prf[1].back());
        }
        int64_t res = 0;
        for (int i = 0; i < bd[1].size(); i++) {
            res = std::max(res, get_cum(0, 0, bd[1][i]) + get_cum(1, bd[1][i], n + 1));
        }
        return res;
    }

    std::vector<std::vector<std::vector<int64_t>>> dp(n - 1);

    for (int i = 0; i < n - 1; i++) {
        dp[i].assign(bd[i].size(), std::vector<int64_t>(bd[i + 1].size(), 0));
    }
    for (int a = 0; a < bd[0].size(); a++) {
        for (int b = 0; b < bd[1].size(); b++) {
            if (bd[0][a] <= bd[1][b]) {
                int id = lb(0, bd[1][b]);
                dp[0][a][b] = prf[0][id] - prf[0][a];
            } else {
                int id = lb(1, bd[0][a]);
                dp[0][a][b] = prf[1][id] - prf[1][b];
            }
        }
    }

    auto get = [&](int i, int a, int b, int c) -> int64_t {
        int x = bd[i][a], y = bd[i + 1][b], z = bd[i + 2][c];
        if (x > y && y < z) {
            if (b > 0) {
                return -1e18;
            } else {
                if (x >= z) {
                    return 0;
                } else {
                    // return get_cum(i + 1, x, z);
                    return prf2[i][a] - prf3[i + 2][c];
                }
            }
        }
        if (y >= z) {
            // return get_cum(i + 2, z, y);
            return prf2[i + 1][b] - prf[i + 2][c];
        } else {
            // return get_cum(i + 1, y, z);
            return prf3[i + 2][c] - prf[i + 1][b];
        }
        assert(false);
    };
    for (int i = 0; i + 2 < n; i++) {
        for (int a = 0; a < bd[i].size(); a++) {
            for (int b = 0; b < bd[i + 1].size(); b++) {
                int64_t val = dp[i][a][b];
                for (int c = 0; c < bd[i + 2].size(); c++) {
                    int64_t dlt = get(i, a, b, c);
                    // dlt = get(i, a, b, c) - get(i, a, b, 0);
                    dp[i + 1][b][c] = std::max(dp[i + 1][b][c], val + dlt);
                }
            }
        }
    }

    int64_t res = 0;
    for (int a = 0; a < bd[n - 2].size(); a++) {
        for (int b = 0; b < bd[n - 1].size(); b++) {
            res = std::max(res, dp[n - 2][a][b]);
        }
    }

    return res;
}