#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
static_assert(D >= 1, "Vector dimension must be greater than zero!");
template<typename... Args>
Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
}
};
template<typename T>
struct Vec<1, T> : public vector<T> {
Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {
}
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
int n = N, m = M;
Vec<2, array<int, 2>> a(n);
for (int i = 0; i < m; i++) {
a[X[i]].push_back({Y[i], W[i]});
}
for (int i = 0; i < n; i++) {
a[i].push_back({n, 0});
sort(a[i].begin(), a[i].end());
}
Vec<2, long long> prev(a[0].size(), a[1].size(), 0);
for (int x = 0; x < a[0].size(); x++) {
for (int y = 0; y < a[1].size(); y++) {
for (int i = x; i < a[0].size(); i++) {
if (a[0][i][0] < a[1][y][0]) prev[x][y] += a[0][i][1];
}
for (int i = y; i < a[1].size(); i++) {
if (a[1][i][0] < a[0][x][0]) prev[x][y] += a[1][i][1];
}
}
}
for (int col = 2; col < n; col++) {
Vec<2, long long> dp(a[col - 1].size(), a[col].size(), 0);
for (int x = 0; x < a[col - 2].size(); x++) {
for (int y = 0; y < a[col - 1].size(); y++) {
for (int z = 0; z < a[col].size(); z++) {
long long val = 0;
for (int i = y; i < a[col - 1].size(); i++) {
if (a[col - 1][i][0] >= a[col - 2][x][0] && a[col - 1][i][0] < a[col][z][0]) val += a[col - 1][i][1];
}
for (int i = z; i < a[col].size(); i++) {
if (a[col][i][0] < a[col - 1][y][0]) val += a[col][i][1];
}
dp[y][z] = max(dp[y][z], prev[x][y] + val);
}
}
}
prev = dp;
}
long long ans = 0;
for (vector<long long> v : prev) {
ans = max(ans, *max_element(v.begin(), v.end()));
}
return ans;
}
