#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[n+5][n+5][2];
memset(dp,0,sizeof(dp));
for(int x=1;x<=n;x++){
//go up
int cur=-1e15;
int cnt=0;
for(int y=1;y<=n;y++){
cur=max(cur+arr[x-1][y],dp[x-1][y][0]);
if(x>1){
cur=max(cur,dp[x-2][0][0]);
}
dp[x][y][0]=cur;
dp[x][y][1]=cur;
cnt+=arr[x-1][y];
}
if(x>1){
dp[x][n][0]=max(dp[x][n][0],dp[x-2][n][0]+cnt);
dp[x][n][1]=dp[x][n][0];
}
//go down
cur=-1e15;
for(int y=n;y>=0;y--){
cur=max(cur,dp[x-1][y][1]);
cur+=arr[x][y];
dp[x][y][1]=max(dp[x][y][1],cur);
}
//show(x,x);
//for(int y=0;y<=n;y++){
//cout << dp[x][y][0] << " ";
//}
//cout << "\n";
//for(int y=0;y<=n;y++){
//cout << dp[x][y][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;
}
