#include "fish.h"
#include <vector>
#include <cstdint>
#include <iostream>
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
int h = 8 + 1;
int64_t sum_up_to[N][h];
for (int x = 0; x < N; x++) {
for (int y = 0; y < h; y++) {
sum_up_to[x][y] = 0;
}
}
for (int i = 0; i < M; i++) {
sum_up_to[X[i]][Y[i] + 1] = W[i];
}
for (int x = 0; x < N; x++) {
int64_t accum = 0;
sum_up_to[x][0] = accum;
for (int y = 1; y < h; y++) {
accum += sum_up_to[x][y];
sum_up_to[x][y] = accum;
}
}
int64_t dp[N][h][h];
for (int i = 0; i < N; i++) {
for (int x = 0; x < h; x++) {
for (int y = 0; y < h; y++) {
dp[i][x][y] = INT64_MIN;
}
}
}
for (int x = 0; x < h; x++) {
dp[0][x][0] = 0;
}
for (int i = 1; i < N; i++) {
for (int x = 0; x < h; x++) {
for (int y = 0; y < h; y++) {
if (x == y) {
dp[i][x][y] = 0;
for (int z = 0; z < h; z++) {
dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z]);
}
} else if (x > y) {
dp[i][x][y] = 0;
for (int z = 0; z < h; z++) {
if (x > y && x > z) {
dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z] + sum_up_to[i - 1][x] - sum_up_to[i - 1][std::max(y, z)]);
} else {
dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z]);
}
}
} else {
dp[i][x][y] = 0;
{
for (int z = 0; z < h; z++) {
dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z]);
}
}
dp[i][x][y] += sum_up_to[i][y] - sum_up_to[i][x];
}
}
}
// std::cout << dp[i][0][0] << ' ' << dp[i][0][1] << ' ' << dp[i][1][0] << ' ' << dp[i][1][1] << '\n';
}
int64_t best = 0;
for (int x = 0; x < h; x++) {
for (int y = 0; y < h; y++) {
best = std::max(best, dp[N - 1][x][y]);
}
}
return best;
}
