#include "fish.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
#define mxn 300
long long dp[mxn+2][mxn+2][2];
long long p[mxn+2][mxn+2];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
int n = N, m = M;
for (int i=0; i<m; i++) {
int x = X[i], y = Y[i], w = W[i];
p[x+1][y+1] += w;
}
for (int i=0; i<=n; i++) {
partial_sum(p[i], p[i]+n+1, p[i]);
}
for (int j=1; j<=n; j++) dp[0][j][0] = dp[0][j][1] = -1e18;
dp[0][0][0] = dp[0][0][1] = 0;
for (int i=1; i<=n+1; i++) {
for (int j=0; j<=n; j++) {
dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][1] + (p[i][j] - p[i][0]));
dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][0]);
for (int k=0; k<=j; k++) dp[i][j][0] = max(dp[i][j][0], dp[i-1][k][0] + (p[i-1][j] - p[i-1][k]));
for (int k=n; k>=j; k--) dp[i][j][1] = max(dp[i][j][1], dp[i-1][k][1] + (p[i][k] - p[i][j]));
}
}
return dp[n+1][0][1];
}
