#include "fish.h"
#include <vector>
#include <iostream>
using namespace std;
int const N=310;
long long dp[N][N][2]={};
long long gr[N][N]={},pre[N][N]={}; // 0 if we are updating it from behind 1 if being updated from
long long sol(int n)
{
for (int i=1;i<=n;i++)
for (int j=0;j<n;j++)
pre[i][j+1]=pre[i][j]+gr[i][j];
for (int i=1;i<=n;i++)
dp[0][i][0]=dp[0][i][1]=-1e17;
long long mx=0;
for (int i=1;i<=n;i++)
{
for (int j=0;j<=n;j++)
{
for (int k=0;k<=n;k++)
{
if (j<k)
{
dp[i][j][0]=max(dp[i][j][0],dp[i-1][k][0]+pre[i][k]-pre[i][j]);
dp[i][k][1]=max(dp[i][k][1],dp[i-1][k][0]+pre[i][k]-pre[i][j]);
}
else
{
dp[i][j][0]=max(dp[i][j][0],dp[i-1][k][1]+pre[i-1][j]-pre[i-1][k]);
dp[i][j][1]=max(dp[i][j][1],dp[i-1][k][1]+pre[i-1][j]-pre[i-1][k]);
}
dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][0]+pre[i][j]);
mx=max(mx,max(dp[i][j][1],dp[i][j][0]));
}
}
}
return mx;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W)
{
for (int i=0;i<M;i++)
gr[X[i]+1][Y[i]]=W[i];
return sol(N);
}
