#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
const int MAX = 1e5 + 5;
bool markLow[MAX];
vector<ii> g[MAX];
vector<long long> S[MAX];
vector<vector<long long>> f[MAX];
long long calcCost(int col, int L, int R) {
int l = lower_bound(g[col].begin(), g[col].end(), ii(L, 0)) - g[col].begin();
int r = upper_bound(g[col].begin(), g[col].end(), ii(R, 0)) - g[col].begin() - 1;
if (l <= r)
return S[col][r] - (l ? S[col][l - 1] : 0);
return 0;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int i = 0; i < M; i++) {
g[X[i]].emplace_back(Y[i], W[i]);
if (!Y[i])
markLow[X[i]] = true;
}
for (int i = 0; i < N; i++) {
if (!markLow[i])
g[i].emplace_back(0, 0);
g[i].emplace_back(N, 0);
}
for (int i = 0; i < N; i++) {
sort(g[i].begin(), g[i].end());
S[i].resize(g[i].size());
S[i][0] = g[i][0].second;
for (int j = 1; j < g[i].size(); j++)
S[i][j] = S[i][j - 1] + g[i][j].second;
f[i].resize(g[i].size(), vector<long long>(2));
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < g[i].size(); j++) {
if (i > 1) {
for (int t = 0; t < g[i - 2].size(); t++) {
long long tmp = f[i - 2][t][1] + calcCost(i - 1, 0, max(g[i - 2][t].first, g[i][j].first));
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
}
} else {
long long tmp = calcCost(0, 0, g[i][j].first);
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
}
for (int t = 0; t < g[i - 1].size(); t++) {
if (g[i - 1][t].first <= g[i][j].first) {
f[i][j][0] = max(f[i][j][0], f[i - 1][t][0] + calcCost(i - 1, g[i - 1][t].first, g[i][j].first));
f[i][j][1] = max(f[i][j][1], f[i - 1][t][0] + calcCost(i - 1, g[i - 1][t].first, g[i][j].first));
}
if (g[i - 1][t].first >= g[i][j].first)
f[i][j][1] = max(f[i][j][1], f[i - 1][t][1] + calcCost(i, g[i][j].first, g[i - 1][t].first));
}
}
}
long long rs = 0;
for (int j = 0; j < f[N - 1].size(); j++)
rs = max({rs, f[N - 1][j][0], f[N - 1][j][1]});
return rs;
}
//int main() {
// freopen("../_input", "r", stdin);
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
//
// std::vector<int> X(M), Y(M), W(M);
// for (int i = 0; i < M; ++i) {
// assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
// }
//
// long long result = max_weights(N, M, X, Y, W);
// printf("%lld\n", result);
// return 0;
//}
