#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mat[305][305],psum[305][305],dp[305][305];
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W){
for(int i=0;i<M;i++){
mat[Y[i]+1][X[i]+1]=W[i];
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
psum[i][j]=mat[i][j]+psum[i-1][j];
}
}
for(int j=1;j<=N;j++){
dp[0][j]=dp[N][j-1];
for(int i=1;i<=N;i++){
// no usar i,j
dp[i][j]=dp[i-1][j];
//usar i,j;
for(int k=0;k<=N;k++){
if(k<=i){
dp[i][j]=max(dp[i][j],dp[k][j-1]-psum[k][j]+psum[i][j-1]-psum[k][j-1]+psum[i][j+1]);
}else{
dp[i][j]=max(dp[i][j],dp[k][j-1]-psum[i][j]+psum[i][j+1]);
}
}
if(j>=2){
for(int k=0;k<=N;k++){
if(k<=i){
dp[i][j]=max(dp[i][j],dp[k][j-2]+psum[i][j-1]-psum[k][j-1]+psum[i][j+1]);
}else{
dp[i][j]=max(dp[i][j],dp[k][j-2]+psum[i][j+1]);
}
}
/*if(j>=3){
dp[i][j]=max(dp[i][j],dp[N][j-3]+psum[i][j-1]+psum[i][j+1]);
}*/
}
}
}
return dp[N][N];
}
