#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());
long long max_weights(int32_t n, int32_t m, vector<int32_t>a, vector<int32_t>b, vector<int32_t>w){
int arr[n+5][n+5];
memset(arr,0,sizeof(arr));
for(int x=0;x<m;x++){
a[x]++;
b[x]++;
arr[a[x]][b[x]]+=w[x];
}
/*
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;
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;
for(int x=h;x>=0;x--){
ans=max(ans,dp(index+1,x,1)+add);
add+=arr[index+1][x];
}
}
return memo[index][h][amos]=ans;
}
*/
int dp[n+5][n+5][2];
for(int x=0;x<=n;x++){
for(int y=0;y<=n;y++){
dp[x][y][0]=dp[x][y][1]=-1e15;
}
}
dp[0][0][0]=0;
for(int index=1;index<=n;index++){
//go up
int add=-1e15;
int add2=0;
for(int h=0;h<=n;h++){
add=max(add+arr[index-1][h],dp[index-1][h][0]);
dp[index][h][0]=max(dp[index][h][0],add);
add2+=arr[index-1][h];
if(h==n){
dp[index][h][1]=max(dp[index][h][0],dp[index][h][1]);
if(index>2){
dp[index][h][1]=max(dp[index][h][1],add2+dp[index-2][h][0]);
}
}
}
//go down
add=-1e15;
for(int h=n;h>=0;h--){
add=max(add,dp[index-1][h][1]);
//show(add,add);
dp[index][h][1]=max(dp[index][h][1],add);
add+=arr[index][h];
}
dp[index][0][0]=dp[index-1][0][1];
//show(index,index);
//for(int x=1;x<=n;x++){
//cout << dp[index][x][0] << " ";
//}
//cout << "\n";
//for(int x=1;x<=n;x++){
//cout << dp[index][x][1] << " ";
//}
//cout << "\n\n";
}
int maxi=0;
for(int x=1;x<=n;x++){
for(int y=0;y<=n;y++) maxi=max({maxi,dp[x][y][0],dp[x][y][1]});
}
return maxi;
}
