#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+5;
ll pre[MAXN][10];
ll dp[MAXN][10][10];
long long max_weights(int N, int M, vector<int> X, vector<int> Y,
vector<int> W) {
for (int i = 0; i < M; ++i) {
pre[X[i]+1][Y[i]+1] += W[i];
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= 9; ++j) {
pre[i][j] += pre[i][j-1];
}
}
ll ans = 0;
for (int i = 2; i <= N; ++i) { for (int j = 0; j <= 9; ++j) {
for (int k = 0; k <= 9; ++k) {
if (i == 2) {
if (j >= k) {
dp[i][j][k] = pre[i-1][j] - pre[i-1][k];
} else {
dp[i][j][k] = pre[i][k] - pre[i][j];
}
ans = max(ans, dp[i][j][k]);
continue;
}
for (int l = 0; l <= 9; ++l) {
ll add = 0;
if (l <= k && k <= j) {
add = pre[i-1][j] - pre[i-1][k]; // 1 2 3
} else if (l >= k && j >= l) {
add = pre[i-1][j] - pre[i-1][l]; // 2 1 3
} else if (l>=k && l>= j && j >= k) {
add = 0; // 3 1 2
} else if (k >= j) {
add = pre[i][k] - pre[i][j]; // 1 3 2 and 2 3 1 and 3 2 1
}
dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l] + add);
}
ans = max(ans, dp[i][j][k]);
}
}
}
return ans;
}
