#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 310;
int n;
ll s[maxn][maxn];
ll maxSuffix[maxn];
ll dp[maxn][maxn][maxn];
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++)
{
X[i]++; Y[i]++;
s[ X[i] ][ Y[i] ] += W[i];
}
for(int i = 1 ; i <= n ; i++)
for(int j = n ; j >= 0 ; j--)
s[i][j] += s[i][j + 1];
for(int hI = 0 ; hI <= n ; hI++)
{
for(int hB = 0 ; hB <= n ; hB++)
{
if( hB <= hI )
dp[n][hI][hB] = 0;
else
dp[n][hI][hB] = s[n][hI + 1] - s[n][hB + 1];
}
}
for(int i = n - 1 ; i > 0 ; i--)
{
for(int hI = 0 ; hI <= n ; hI++)
{
// Calculating dp[i][hI][0]
for(int x = 0 ; x <= n ; x++)
{
if( x <= hI )
dp[i][hI][0] = max( dp[i][hI][0] , dp[i + 1][x][hI] );
else
dp[i][hI][0] = max( dp[i][hI][0] , dp[i + 1][x][hI] + s[i][hI + 1] - s[i][x + 1] );
}
// Calculating dp[i][hI][hB] (hB > 0)
ll maxFirst = dp[i + 1][0][hI];
for(int x = n ; x >= 0 ; x--)
maxSuffix[x] = max( maxSuffix[x + 1] , dp[i + 1][x][hI] + s[i][hI + 1] - s[i][x + 1] );
for(int hB = 1 ; hB <= n ; hB++)
{
ll& ans = dp[i][hI][hB];
maxFirst = max( maxFirst , dp[i + 1][hB][hI] );
if( hB <= hI )
{
ans = dp[i][hI][0];
continue;
}
ans = max( maxFirst + s[i][hI + 1] - s[i][hB + 1] , maxSuffix[hB + 1] );
}
}
}
ll ans = 0;
for(int i = 0 ; i <= n ; i++)
ans = max( ans , dp[1][i][0] );
return ans;
}
