#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
struct fish {
int x, y, w;
};
int M, N;
vector<fish> f;
vector<map<vector<int>,long long>> memo;
bool comp(const fish &a, const fish &b) {
return(a.x < b.x || (a.x == b.y && a.y < b.y));
}
bool comp2 (const fish &a, const fish &b) {
if (a.x < b.x) return true;
if (a.x == b.x && a.y < b.y) return true;
if (a.x == b.x && a.y == b.y && a.w < b.w) return true;
return false;
}
long long dp(int i, int bas, int SLD, int basGauche, int curr) {
if (i >= M) return 0;
if (f[i].x == curr + 1) {
curr = f[i].x;
int index = lower_bound(f.begin(), f.end(), fish({f[i].x, SLD + 1, -1}), comp2) - f.begin();
basGauche = bas;
bas = N;
SLD = -1;
return dp(index, bas, SLD, basGauche, curr);
}
else if (f[i].x > curr + 1) {
curr = f[i].x;
basGauche = N;
bas = N;
SLD = -1;
}
if (memo[i].count({bas, SLD, basGauche})) return memo[i][{bas, SLD, basGauche}];
long long take = -1;
if (f[i].x && f[i].y < basGauche) {
take = dp(i + 1, min(bas, f[i].y), SLD, basGauche, curr) + f[i].w;
}
else if (f[i].x < N - 1) {
take = dp(i + 1, min(bas, f[i].y), f[i].y, basGauche, curr) + f[i].w;
}
long long notake = dp(i + 1, bas, SLD, basGauche, curr);
return memo[i][{bas, SLD, basGauche}] = max(take, notake);
}
long long max_weights(int NN, int MM, vector<int> X, vector<int> Y,vector<int> W) {
ios::sync_with_stdio(false);
M = MM, N = NN;
f.resize(M);
for (int i = 0; i < M; i++) f[i] = fish({X[i], Y[i], W[i]});
sort(f.begin(), f.end(), comp);
memo.resize(M);
return dp(0, N, -1, N, -10);
}
