#include "fish.h"
#include <bits/stdc++.h>
#define MAX 100001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
for(int i=0;i<b;i++){\
cin >> a[i];\
}\
}
#define inputvec(a,b){\
for(int i=0;i<b;i++){\
ll num;\
cin >> num;\
a.pb(num);\
}\
}
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << x << " ";\
}\
cout << "\n";\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef double db;
typedef long double ldb;
ll n,q,t=1,m,n2,m2,k,cnt=0,a[MAX],b[MAX],d[MAX],x,y,z,x2,y2,z2,res1=0,cnt1,cnt2,cnt3;
ll dp[301][301];
ll arr[301][301];
ll comp[301][301][301];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
bool ok=false;
bool ok2=false;
bool ok3=false;
for(int i=0;i<M;i++){
if(X[i]%2){
ok=true;
}
if(Y[i]!=0){
ok2=true;
}
if(X[i]>1){
ok3=true;
}
a[X[i]]=W[i];
if(X[i]==0){
b[Y[i]]=W[i];
}
else{
d[Y[i]]=W[i];
}
}
if(!ok){
ll res=0;
for(int i=0;i<M;i++){
res+=W[i];
}
return res;
}
if(!ok2){
ll res=0;
ll dp[N][2];
dp[0][0]=dp[0][1]=0;
dp[1][0]=a[1];
dp[1][1]=a[0];
for(int i=2;i<N;i++){
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1];
dp[i][0]=max(dp[i][0],dp[i-1][1]+a[i]);
dp[i][1]=max(dp[i][1],max(dp[i-2][0],dp[i-2][1])+a[i-1]);
}
return max(dp[N-1][0],dp[N-1][1]);
}
if(!ok3){
for(int i=1;i<N;i++){
b[i]+=b[i-1];
d[i]+=d[i-1];
}
ll res=max(b[N-1],d[N-1]);
if(N>2){
for(int i=0;i<N;i++){
res=max(res,b[i]+d[N-1]-d[i]);
}
}
return res;
}
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
dp[i][j]=0;
arr[i][j]=0;
}
}
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
for(int z=0;z<=N;z++){
comp[i][j][z]=0;
}
}
}
for(int i=0;i<M;i++){
arr[X[i]+1][Y[i]+1]=(ll) W[i];
}
for(int z=1;z<=N;z++){
for(int i=z;i<=N;i++){
for(int j=1;j<=N;j++){
comp[z][i][j]=max(comp[z][i-1][j],comp[z][i][j-1]);
comp[z][i][j]=max(comp[z][i][j],comp[z][i-1][j-1]+arr[i][j]);
}
}
}
for(int i=2;i<=N;i++){
for(int z=0;z<=N;z++){
a[z]=b[z]=d[z]=0;
}
ll mx=0;
for(int j=N;j>=0;j--){
if(dp[i-1][j]>mx){
mx=dp[i-1][j];
}
dp[i][j]=max(dp[i][j],mx);
mx+=arr[i][j];
}
for(int z=i-1;z>=1;z--){
ll h=(z>1);
mx=0;
for(int j=N;j>=0;j--){
if(dp[z-1][j]>mx){
mx=dp[z-1][j];
}
d[j]=mx;
mx+=h*arr[z][j];
}
mx=0;
for(int j=0;j<=N;j++){
mx=max(mx,d[j]+arr[z][j]-comp[z+1][i-1][j]);
dp[i][j]=max(dp[i][j],mx+comp[z+1][i-1][j]);
}
}
}
ll res=0;
for(int i=0;i<=N;i++){
res=max(res,dp[N][i]);
}
return res;
}
