#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> dp[2][6];
    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;
        }
    }
    dp[0][0].push_back(0); dp[0][0].push_back(-INF);
    dp[1][0].push_back(-INF); dp[1][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}); it--;
                    auto tmp = pref[i-1].lower_bound({j.first, -INF});
                    int a1 = it->second + tmp->second;
                    if(j.first == 0) {
                        a1 = max(a1, dp[1][i-1][0]);
                    }
                    if(i == 1) a1 = 0;
                    dp[k][i].push_back(a1);
                    if(i < N) {
                        auto tmp = pref[i+1].lower_bound({j.first, -INF});
                        s[0][i].insert({j.first, max(dp[k][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))});
                    }
                } else {
                    auto it = s[1][i-1].lower_bound({j.first, -INF});
//                    cout << "process " << i << " " << j.first << " " << k << endl;
//                    for(auto it2 : s[1][i-1]) cout << it2.first << " " << -it2.second << endl;
                    dp[k][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});
                    }
                }
//                cout << i << " " << j.first << " " << k << " " << dp[k][i].back() << endl;
                ans = max(ans, dp[k][i].back());
            }
            cnt += j.second;
        }
    }
    return ans;
#undef int
}