#include "fish.h"
#include <vector>
#include <cstdio>
using namespace std;
using ll = long long;
const int N_MAX = 305;
const int Y_MAX = 10;
ll pre[N_MAX][N_MAX];
ll dp[N_MAX][Y_MAX][Y_MAX];
bool got[N_MAX][Y_MAX][Y_MAX];
int N;
ll f(int i, int j, int k) {
if (i < 0) return 0;
if (got[i][j][k]) return dp[i][j][k];
ll ans = f(i-1, 0, j) + pre[i][j];
for (int l = 1; l <= 8; l++) {
ll v = f(i-1, l, j);
if (l < j) {
v += pre[i][j] - pre[i][l];
}
if (l > j) {
v += pre[i+1][max(l,k)] - pre[i+1][max(j,k)];
}
ans = max(ans, v);
}
got[i][j][k] = true;
//printf("i=%d j=%d k=%d -> %lld\n", i, j, k, ans);
return dp[i][j][k] = ans;
}
ll max_weights(
int N, int M, vector<int> X, vector<int> Y, vector<int> W
) {
::N = N;
for (int i = 0; i < M; i++)
pre[X[i]][Y[i]+1] = W[i];
for (int i = 0; i < N; i++)
for (int j = 1; j <= N; j++)
pre[i][j] += pre[i][j-1];
return f(N-1, 0, 0);
}
