#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

constexpr long long inf = (long long)1e18 + 7;

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    vector<vector<pair<int, int>>> fish(n);
    for (int i = 0; i < m; ++i) {
        fish[x[i]].emplace_back(y[i], w[i]);
    }
    vector<vector<long long>> pr_sum(n);
    for (int i = 0; i < n; ++i) {
        sort(fish[i].begin(), fish[i].end());
        fish[i].emplace_back(n, 0);
        pr_sum[i].assign(fish[i].size() + 1, 0);
        for (int j = 0; j < (int)fish[i].size(); ++j) {
            pr_sum[i][j + 1] = pr_sum[i][j] + fish[i][j].second;
        }
    }
    vector<vector<long long>> dp1(n), dp2(n), dp1_max(n), dp2_max(n);
    dp1[1].assign(fish[1].size(), 0);
    dp1_max[1].assign(fish[1].size() + 1, -inf);
    for (int cnt = 0; cnt < (int)fish[1].size(); ++cnt) {
        int pos = lower_bound(fish[0].begin(), fish[0].end(), make_pair(fish[1][cnt].first, 0)) - fish[0].begin();
        dp1[1][cnt] = pr_sum[0][pos];
        dp1_max[1][cnt + 1] = max(dp1_max[1][cnt], dp1[1][cnt] - pr_sum[1][cnt]);
    }
    dp2[1].assign(fish[0].size(), 0);
    dp2_max[1].assign(fish[0].size() + 1, -inf);
    for (int cnt = (int)fish[0].size() - 1; cnt >= 0; --cnt) {
        int pos = lower_bound(fish[1].begin(), fish[1].end(), make_pair(fish[0][cnt].first, 0)) - fish[1].begin();
        dp2[1][cnt] = pr_sum[1][pos];
        dp2_max[1][cnt] = max(dp2_max[1][cnt + 1], dp2[1][cnt]);
    }
    for (int i = 2; i < n; ++i) {
        dp1[i].assign(fish[i].size(), 0);
        for (int cnt_nw = 0; cnt_nw < fish[i].size(); ++cnt_nw) {
            int cnt_prv = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(fish[i][cnt_nw].first, 0)) - fish[i - 1].begin();
            int pos = lower_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(fish[i][cnt_nw].first, 0)) - fish[i - 1].begin();
            dp1[i][cnt_nw] = max(dp1[i][cnt_nw], dp1_max[i - 1][cnt_prv] + pr_sum[i - 1][pos]);
        }
        for (int cnt_prv2 = 0; cnt_prv2 < fish[i - 2].size(); ++cnt_prv2) {
            for (int cnt_nw = 0; cnt_nw < fish[i].size(); ++cnt_nw) {
                int pos_prv = lower_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(fish[i - 2][cnt_prv2].first, 0)) - fish[i - 1].begin();
                int pos_nw = lower_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(fish[i][cnt_nw].first, 0)) - fish[i - 1].begin();
                if (pos_prv >= pos_nw) {
                    dp1[i][cnt_nw] = max(dp1[i][cnt_nw], dp2[i - 1][cnt_prv2]);
                } else {
                    dp1[i][cnt_nw] = max(dp1[i][cnt_nw], dp2[i - 1][cnt_prv2] + pr_sum[i - 1][pos_nw] - pr_sum[i - 1][pos_prv]);
                }
            }
        }
        dp1_max[i].assign(fish[i].size() + 1, -inf);
        for (int cnt_nw = 0; cnt_nw < fish[i].size(); ++cnt_nw) {
            dp1_max[i][cnt_nw + 1] = max(dp1_max[i][cnt_nw], dp1[i][cnt_nw] - pr_sum[i][cnt_nw]);
        }
        dp2[i].assign(fish[i - 1].size(), 0);
        for (int cnt_prv = 0; cnt_prv < fish[i - 1].size(); ++cnt_prv) {
            int pos = lower_bound(fish[i].begin(), fish[i].end(), make_pair(fish[i - 1][cnt_prv].first, 0)) - fish[i].begin();
            dp2[i][cnt_prv] = max(dp2[i][cnt_prv], dp1[i - 1][cnt_prv] + pr_sum[i][pos]);
        }
        for (int cnt_prv = 0; cnt_prv < fish[i - 1].size(); ++cnt_prv) {
            int cnt_prv2 = lower_bound(fish[i - 2].begin(), fish[i - 2].end(), make_pair(fish[i - 1][cnt_prv].first, 0)) - fish[i - 2].begin();
            int pos = lower_bound(fish[i].begin(), fish[i].end(), make_pair(fish[i - 1][cnt_prv].first, 0)) - fish[i].begin();
            dp2[i][cnt_prv] = max(dp2[i][cnt_prv], dp2_max[i - 1][cnt_prv2] - pr_sum[i - 1][cnt_prv] + pr_sum[i][pos]);
        }
        dp2_max[i].assign(fish[i - 1].size() + 1, -inf);
        for (int cnt_prv = (int)fish[i - 1].size() - 1; cnt_prv >= 0; --cnt_prv) {
            dp2_max[i][cnt_prv] = max(dp2_max[i][cnt_prv + 1], dp2[i][cnt_prv]);
        }
    }
    long long ans = 0;
    for (int i = 0; i < (int)dp1[n - 1].size(); ++i) {
        ans = max(ans, dp1[n - 1][i]);
    }
    for (int i = 0; i < (int)dp2[n - 1].size(); ++i) {
        ans = max(ans, dp2[n - 1][i]);
    }
    return ans;
}