#include "fish.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<int>x(M+1),y(M+1);
vector<vector<int>>w(N+2,vector<int>(N+2,0));
vector<vector<int>>dp(N+2,vector<int>(N+2,0));
for(int i=0;i<M;i++){
x[i+1]=X[i]+1;
y[i+1]=Y[i]+1;
}
for(int k=1;k<=M;k++){
int i=x[k], j=y[k];
w[i][j]=W[k-1];
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
w[i][j]+=w[i][j-1];
}
}
for(int i=1;i<=1;i++){
for(int j=1;j<=N;j++){
int si=w[i-1][j]+w[i+1][j];//ambos
dp[i][j]=max(si-dp[i-1][j],dp[i][j]);
dp[i][j]=max(dp[i-1][j]-w[i][j]+w[i+1][j],dp[i][j]); //solo derecha
dp[i][j]=max(dp[i][j-1],dp[i][j]); //abajo
}
}
for(int i=2;i<=N;i++){
for(int j=1;j<=N;j++){
int si=w[i-1][j]+w[i+1][j];//ambos
dp[i][j]=max(si-dp[i-1][j]+w[i][j],dp[i][j]);
//cout<<"1 "<<si-dp[i-1][j]+w[i][j]<<"\n";
dp[i][j]=max(dp[i-1][j]-w[i][j]+w[i+1][j],dp[i][j]); //solo derecha
//cout<<"2 "<<dp[i-1][j]-w[i][j]+w[i+1][j]<<"\n";
dp[i][j]=max(dp[i][j-1],dp[i][j]); //abajo
dp[i][j]=max(dp[i-1][j],dp[i][j]); //lado
//cout<<"3 "<<dp[i][j-1]<<"\n";
}
}
for(auto v: dp){
//for(int x: v) cout<<x<<" ";
//cout<<"\n";
}
return dp[N][N];
}
