#include <bits/stdc++.h>

#include "fish.h"

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

const ll inf = 1e18;
mt19937 rnd(234);

int n, m;
vector<int> w;
vector<pair<int, int>> poss;
vector<vector<pair<ll, ll>>> bbr_cst;
vector<vector<ll>> bbr;

ll solve() {
    bbr.assign(n, vector<ll>());
    bbr_cst.assign(n, vector<pair<ll, ll>>());
    for (int i = 0; i < m; i += 1) {
        auto [x, y] = poss[i];
        bbr[x].push_back(y);
        bbr_cst[x].push_back(make_pair(y, w[i]));
    }
    for (int x = 0; x < n; x += 1) {
        sort(all(bbr[x]));
        sort(all(bbr_cst[x]));
    }
    auto get_bbr = [&](int i) -> vector<ll> {
        if (i < 0 || i >= n) {
            return {};
        }
        return bbr[i];
    };
    auto uniq = [&](vector<ll> &a) -> void {
        a.resize(unique(all(a)) - a.begin());
    };
    auto uniq_ret = [&](vector<ll> a) -> vector<ll> {
        uniq(a);
        return a;
    };
    auto mrg = [&](const vector<ll> &a, const vector<ll> &b) -> vector<ll> {
        int asz = (int)a.size();
        int bsz = (int)b.size();
        vector<ll> c(asz + bsz);
        merge(all(a), all(b), c.begin());
        return c;
    };
    auto get_idx = [&](const vector<ll> &a, ll x) -> int {
        auto it = lower_bound(all(a), x);
        if (it == a.end() || *it != x) {
            return -1;
        }
        return it - a.begin();
    };
    auto get_summ_on_seg = [&](const vector<ll> &vct, const vector<ll> &psms, ll xl, ll xr) -> ll {
        if (xl > xr) {
            return 0;
        }
        int l = lower_bound(all(vct), xl) - vct.begin();
        int r = upper_bound(all(vct), xr) - vct.begin();
        return psms[r] - psms[l];
    };
    vector dp(n + 1, vector(2, vector<ll>()));
    dp[0][0] = {0, -inf};
    dp[0][1] = {-inf, -inf};
    for (int i = 0; i < n; i += 1) {
        auto prev_prev_vct = uniq_ret(mrg({0, inf}, get_bbr(i - 2)));
        auto prev_vct = uniq_ret(mrg({0, inf}, get_bbr(i - 1)));
        auto my_vct = uniq_ret(mrg({0, inf}, get_bbr(i)));
        int prev_prev_sz = (int)prev_prev_vct.size();
        int prev_sz = (int)prev_vct.size();
        int my_sz = (int)(my_vct.size());
        vector<ll> prev_psms(prev_sz + 1, 0), my_psms(my_sz + 1, 0);
        if (i > 0) {
            for (auto [y, cst] : bbr_cst[i - 1]) {
                prev_psms[get_idx(prev_vct, y) + 1] += cst;
            }
        }
        for (auto [y, cst] : bbr_cst[i]) {
            my_psms[get_idx(my_vct, y) + 1] += cst;
        }
        for (int i = 1; i <= prev_sz; i += 1) {
            prev_psms[i] += prev_psms[i - 1];
        }
        for (int i = 1; i <= my_sz; i += 1) {
            my_psms[i] += my_psms[i - 1];
        }
        dp[i + 1][0].assign(my_sz, -inf);
        dp[i + 1][1].assign(my_sz, -inf);
        for (int j = 0; j < my_sz; j += 1) {
            ll y = my_vct[j];
            for (int k = 0; k < prev_sz; k += 1) {
                ll py = prev_vct[k];
                if (py > y) {
                    break;
                }
                dp[i + 1][0][j] = max(dp[i + 1][0][j], dp[i][0][k] + get_summ_on_seg(prev_vct, prev_psms, py, y - 1));
                if (k == 0) {
                    // dp[i + 1][0][j] = max(dp[i + 1][0][j], dp[i][1][k] + get_summ_on_seg(prev_vct, prev_psms, py, y - 1));
                }
            }
        }
        if (i > 0) {
            for (int j = 0; j < my_sz; j += 1) {
                ll y = my_vct[j];
                for (int k = 0; k < prev_prev_sz; k += 1) {
                    ll py = prev_prev_vct[k];
                    dp[i + 1][0][j] = max(dp[i + 1][0][j], max(dp[i - 1][1][k], dp[i - 1][0][k]) + get_summ_on_seg(prev_vct, prev_psms, 0, max(y, py) - 1));
                }
            }
        }
        for (int j = my_sz; j >= 0; j -= 1) {
            ll y = my_vct[j];
            for (int k = prev_sz - 1; k >= 0; k -= 1) {
                ll py = prev_vct[k];
                if (py < y) {
                    break;
                }
                dp[i + 1][1][j] = max(dp[i + 1][1][j], dp[i][1][k] + get_summ_on_seg(my_vct, my_psms, y, py - 1));
                if (k == prev_sz - 1) {
                    dp[i + 1][1][j] = max(dp[i + 1][1][j], dp[i][0][k] + get_summ_on_seg(my_vct, my_psms, y, py - 1));
                }
            }
        }
    }
    ll rs = -inf;
    for (auto x : dp[n][0]) {
        rs = max(rs, x);
    }
    for (auto x : dp[n][1]) {
        rs = max(rs, x);
    }
    return rs;
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N;
    m = M;
    poss.resize(m);
    w = W;
    for (int i = 0; i < m; i += 1) {
        poss[i] = make_pair(X[i], Y[i]);
    }
    ll rs = solve();
    return rs;
}