#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
vector<vector<ll>> vals(N, vector<ll>(10, 0));
for (int i = 0; i < M; ++i) vals[X[i]][Y[i] + 1] += W[i];
for (int i = 0; i < N; ++i) {
for (int j = 1; j < 10; ++j) vals[i][j] += vals[i][j - 1];
}
vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(10, vector<ll>(10, 0)));
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 10; ++j) {
if (!i && !j) continue;
dp[0][i][j] = LLONG_MIN / 2;
}
}
for (int i = 0; i < N; ++i) {
vector<vector<ll>> &prevDp = dp[i], &curDp = dp[i + 1];
for (int prev2 = 0; prev2 < 10; ++prev2) {
for (int prev = 0; prev < 10; ++prev) {
for (int cur = 0; cur < 10; ++cur) {
ll additional = max(0ll, vals[i][prev] - vals[i][cur]);
if (i && cur > max(prev2, prev)) additional += vals[i - 1][cur] - vals[i - 1][max(prev2, prev)];
curDp[prev][cur] = max(curDp[prev][cur], prevDp[prev2][prev] + additional);
}
}
}
}
ll res = 0;
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 10; ++j) res = max(res, dp[N][i][j]);;
}
return res;
}
