#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 300;
const long long INF = 1e9;
long long fish[nax][10];
long long dp[nax][10][10][2];
int n;
long long solve(int i, int mn, int mx, int cv) {
if(i==n) {
if(!cv) return -INF;
return 0LL;
}
long long &ret = dp[i][mn][mx][cv];
if(ret!=-1) return ret;
for(int j=0; j<=8; ++j) {
if(mx>j && !cv) continue;
int s = 0;
for(int k=j+1; k<=8; ++k) {
s += fish[i][k];
ret = max(ret, solve(i+1, j+1, k, (k<=mn)) + s);
}
//no eating
ret = max(ret, solve(i+1, 0, 0, 1));
}
//no wall
if(cv) ret = max(ret, solve(i+1, 9, 9, 1));
return ret;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y,
vector<int> W) {
n = N;
for(int i=0; i<M; ++i) {
fish[X[i]][Y[i]] = W[i];
}
memset(dp, -1, sizeof dp);
return solve(0, 0, 0, 1);
}
