#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W) {
vector<vector<long long>> fish(N+1,vector<long long>(N+1,0));
for(int i = 0;i < M;i++){
fish[X[i]+1][Y[i]+1] = W[i];
}
vector dp(N+1,vector(N+1,0LL));
vector<vector<long long>> pref = fish;
for(int x = 0;x <= N;x++){
for(int y = 1;y <= N;y++) pref[x][y] += pref[x][y-1];
}
auto sum = [&](int x,int l,int r){
if(x > N || x < 0) return 0LL;
if(l == 0) return pref[x][r];
return pref[x][r]-pref[x][l-1];
};
for(int cx = 1;cx <= N;cx++){
for(int cy = 0;cy <= N;cy++){
for(int py = 0;py <= N;py++){
if(cy > py){// cur taller,add back
dp[cx][cy] = max(dp[cx][cy],dp[cx-1][py]-sum(cx,0,py)+sum(cx+1,0,cy)+sum(cx-1,py+1,cy));
}else{// 5 3
dp[cx][cy] = max(dp[cx][cy],dp[cx-1][py]-sum(cx,0,py)+sum(cx+1,0,cy));
}
// if(cx == 1 && py == 0 && cy > 2){
// cout << dp[cx-1][py] << " -" << sum(cx,0,py) << " +" << sum(cx+1,0,cy) << " +" << sum(cx-1,py+1,cy) << "!" << endl;
// }
}
}
}
// for(auto &i:dp){
// for(auto &j:i) cout << j << " ";cout << endl;
// }
// for(auto &i:pref){
// for(auto &j:i) cout << j << " ";cout << endl;
// }
return *max_element(dp[N].begin(),dp[N].end());
}
