#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mat[305][305],psum[305][305],dp[305][305],maxi;
long long 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 i=N;i>=1;i--){
for(int j=1;j<=N;j++){
cout << psum[i][j] << ' ';
}
cout << '\n';
}*/
for(int j=1;j<=N;j++){
dp[0][j]=maxi;
/*for(int i=0;i<=N;i++){
dp[0][j]=max(dp[0][j],dp[i][j-1]);
}*/
for(int i=1;i<=N;i++){
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]);
}else{
dp[i][j]=max(dp[i][j],dp[k][j-1]-psum[k][j]);
}
if(k<i){
dp[i][j]=max(dp[i][j],dp[k][j-2]+psum[i][j-1]-psum[k][j-1]);
}else{
dp[i][j]=max(dp[i][j],dp[k][j-2]);
}
}
maxi=max(maxi,dp[i][j]);
}
}
/*for(int i=N;i>=1;i--){
for(int j=1;j<=N;j++){
cout << dp[i][j] << ' ';
}
cout << '\n';
}*/
return maxi;
}
