#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,vector<long long>(N,0));
for(int i = 0;i < M;i++){
fish[X[i]][Y[i]] = W[i];
}
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];
if(l > r) return 0LL;
return pref[x][r]-pref[x][l-1];
};
vector dpinc(N,vector(N,0LL));
vector dpdec(N,vector(N,0LL));
auto vmax = [&](vector<long long>& v){
return *max_element(v.begin(),v.end());
};
for(int cx = 1;cx < N;cx++){
// dp inc
for(int py = 0;py < N;py++){
for(int cy = py;cy < N;cy++){
dpinc[cx][cy] = max(dpinc[cx][cy],dpinc[cx-1][py]+sum(cx-1,py+1,cy));
}
}
// dp dec
for(int py = 0;py < N;py++){
for(int cy = 0;cy <= py;cy++){
dpdec[cx][cy] = max(dpdec[cx][cy],dpdec[cx-1][py]+sum(cx,cy+1,py));
dpdec[cx][cy] = max(dpdec[cx][cy],dpinc[cx-1][py]+sum(cx,cy+1,py));
}
}
if(cx == 1){
for(int cy = 0;cy < N;cy++){
long long prevV = sum(cx-1,0,cy);
dpinc[cx][cy] = max(dpinc[cx][cy],prevV);
dpdec[cx][cy] = max(dpdec[cx][cy],prevV);
}
continue;
}
// skip one
for(int py = 0;py < N;py++){
for(int cy = 0;cy < N;cy++){
long long prevV = max(dpinc[cx-2][py],dpdec[cx-2][py])+sum(cx-1,0,max(py,cy));
dpinc[cx][cy] = max(dpinc[cx][cy],prevV);
dpdec[cx][cy] = max(dpdec[cx][cy],prevV);
}
}
// skip two
if(cx == 2) continue;
long long two_empty = max(vmax(dpinc[cx-3]),vmax(dpdec[cx-3]));
for(int cy = 0;cy < N;cy++){
dpinc[cx][cy] = max(dpinc[cx][cy],two_empty);
dpdec[cx][cy] = max(dpdec[cx][cy],two_empty);
}
}
long long ans = max(vmax(dpinc[N-1]),vmax(dpdec[N-1]));
for(int ly = 0;ly < N;ly++){
ans = max(ans,dpinc[N-2][ly]+sum(N-1,0,ly));
ans = max(ans,dpdec[N-2][ly]+sum(N-1,0,ly));
}
return ans;
}
