#include "fish.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
int arr[305][305];
int n;
int memo[305][305][2];
int dp(int index, int h, bool amos){
if(index==n) return 0;
if(memo[index][h][amos]!=-1) return memo[index][h][amos];
int ans=-1e15;
//int st=-1;
if(!amos){
//go up
int add=0;
for(int x=h;x<=n;x++){
ans=max(ans,dp(index+1,x,0)+add);
add+=arr[index][x];
}
if(h==n){
ans=max(ans,dp(index,h,1));
if(index+1!=n){
int add2=0;
for(int y=1;y<=n;y++) add2+=arr[index+1][y];
ans=max(ans,dp(index+2,h,1)+add2);
}
}
}
else{
//go down
if(h==0) ans=max(ans,dp(index+1,h,0));
int add=0;
//st=ans;
for(int x=h;x>=0;x--){
ans=max(ans,dp(index+1,x,1)+add);
add+=arr[index+1][x];
}
}
//cout << index << " " << h << " " << amos << " " << ans << " " << st << endl;
return memo[index][h][amos]=ans;
}
long long max_weights(int32_t N, int32_t m, vector<int32_t>a, vector<int32_t>b, vector<int32_t>w){
n=N;
for(int x=0;x<m;x++){
a[x]++;
b[x]++;
arr[a[x]][b[x]]+=w[x];
}
memset(memo,-1,sizeof(memo));
return dp(0,0,0);
}
