#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
ll t[301][301];
ll dp[301][301][2];
ll sum[301][301];
ll max_weights(int N, int M, vector<int> x, vector<int> y, vector<int> w){
ll ans = 0;
for (int i = 0; i < M; i++){
t[x[i]][y[i]] = w[i];
}
for (int i = 0; i < N; i++){
for (int h = 1; h <= 9; h++){
sum[i][h] = t[i][h-1] + sum[i][h-1];
}
if (!i) continue;
for (int a = 0; a <= N; a++){
if (i > 0){
for (int b = 0; b <= a; b++){
dp[i][a][1] = max(dp[i][a][1], dp[i-1][b][1] + (sum[i-1][a] - sum[i-1][b]));
}
for (int b = a; b <= N; b++){
dp[i][a][0] = max(dp[i][a][0], max(dp[i-1][b][0], dp[i-1][b][1]) + (sum[i][b] - sum[i][a]));
}
}
if (i > 1){
for (int c = 0; c <= N; c++){
dp[i][a][1] = max(dp[i][a][1], max(dp[i-2][c][0], dp[i-2][c][1]) + sum[i-1][max(a,c)]);
}
}
ans = max(ans, max(dp[i][a][0], dp[i][a][1]));
}
}
return ans;
}
/*int main(){
int n;
cin >> n;
int m;
cin >> m;
vector<int> x(m);
vector<int> y(m);
vector<int> w(m);
for (int i = 0; i < m; i++){
cin >> x[i];
cin >> y[i];
cin >> w[i];
}
cout << max_weights(n, m, x, y, w);
return 0;
}
*/
