#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
#define int long long
#define INF 1000000000000000000
    int ans = 0;
    vector<int> dp0[N+1], dp1[N+1];
    set<pair<int, int>> fish[N+1], pref[N+1];
    set<pair<int, int>> s[2][N+1];
    for(int i = 0; i < M; i++) {
        fish[X[i]+1].insert({Y[i], W[i]});
    }
    for(int i = 0; i <= N; i++) {
        if(fish[i].empty() || fish[i].begin()->first) fish[i].insert({0,0});
        fish[i].insert({N,0});
        int cnt = 0;
        for(auto j : fish[i]) {
            pref[i].insert({j.first, cnt});
            cnt += j.second;
        }
    }
    vector<pair<int, int>> fish2[N+1];
    for(int i = 0; i <= N; i++) {
        for(auto j : fish[i]) fish2[i].push_back(j);
    }
    dp0[0].push_back(0); dp0[0].push_back(-INF);
    dp1[0].push_back(-INF); dp1[0].push_back(-INF);
    s[0][0].insert({0, 0});
    s[1][0].insert({0, 0});
    s[1][0].insert({N, INF});
    for(int i = 1; i <= N; i++) {
        int cnt = 0;
        for(auto j : fish[i]) {
            for(int k = 0; k < 2; k++) {
                if(k == 0) { // up
                    auto it = s[0][i-1].upper_bound({j.first+1, INF});
                    assert(it != s[0][i-1].begin());
                    it--;
                    auto tmp = pref[i-1].lower_bound({j.first, -INF});
                    assert(tmp != pref[i-1].end());
                    int a1 = it->second + tmp->second;
                    if(j.first == 0) {
                        a1 = max(a1, dp1[i-1][0]);
                    }
                    if(i == 1) a1 = 0;
                    dp0[i].push_back(a1);
                    if(i < N) {
//                        auto tmp = pref[i+1].lower_bound({j.first, -INF});
                        s[0][i].insert({j.first, max(dp0[i].back() - cnt, (s[0][i].size() ? s[0][i].rbegin()->second : -INF))});
//                        s[1][i].insert({j.first, -max(dp[k][i].back() + tmp->second, (s[1][i].size() ? s[1][i].begin()->second : -INF))});
                    }
                    ans = max(ans, dp0[i].back());
                } else {
                    auto it = s[1][i-1].lower_bound({j.first, -INF});
                    assert(it != s[1][i-1].end());
//                    cout << "process " << i << " " << j.first << " " << k << endl;
//                    for(auto it2 : s[1][i-1]) cout << it2.first << " " << -it2.second << endl;
//                    cout << -it->second-cnt << " a" << endl;
                    dp1[i].push_back(-it->second - cnt);
//                    if(i < N) {
//                        auto tmp = pref[i+1].lower_bound({j.first, -INF});
//                        int toins = max(dp[k][i].back() + tmp->second, (s[1][i].size() ? s[1][i].begin()->second : -INF));
//                        s[1][i].insert({j.first, -toins});
//                    }
                    ans = max(ans, dp1[i].back());
                }
//                cout << i << " " << j.first << " " << k << " " << dp[k][i].back() << endl;
            }
            cnt += j.second;
        }
        assert(dp0[i].size() == fish2[i].size());
        if(i < N) {
            for(int j = fish2[i].size()-1; j >= 0; j--) {
                auto tmp = pref[i+1].lower_bound({fish2[i][j].first, -INF});
                s[1][i].insert({fish2[i][j].first, -max(dp0[i][j] + tmp->second, (s[1][i].size() ? -s[1][i].begin()->second : -INF))});
                tmp = pref[i+1].lower_bound({fish2[i][j].first, -INF});
                int toins = max(dp1[i].back() + tmp->second, (s[1][i].size() ? -s[1][i].begin()->second : -INF));
                s[1][i].insert({fish2[i][j].first, -toins});
            }
        }
    }
    return ans;
#undef int
}