#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define inf (long long)(1e15)
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
long long cmax = -inf;
for(int cy = 0;cy < N;cy++){
cmax = max(cmax,dpinc[cx-1][cy]-sum(cx-1,0,cy));
dpinc[cx][cy] = max(dpinc[cx][cy],cmax+sum(cx-1,0,cy));
}
// dp dec
cmax = -inf;
for(int cy = N-1;cy >= 0;cy--){
cmax = max(cmax,dpdec[cx-1][cy]+sum(cx,0,cy));
cmax = max(cmax,dpinc[cx-1][cy]+sum(cx,0,cy));
dpdec[cx][cy] = max(dpdec[cx][cy],cmax-sum(cx,0,cy));
}
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
cmax = -inf;
for(int cy = 0;cy < N;cy++){
cmax = max(cmax,max(dpinc[cx-2][cy],dpdec[cx-2][cy]));
dpinc[cx][cy] = max(dpinc[cx][cy],cmax+sum(cx-1,0,cy));
dpdec[cx][cy] = max(dpdec[cx][cy],cmax+sum(cx-1,0,cy));
}
cmax = -inf;
for(int cy = N-1;cy >= 0;cy--){
cmax = max(cmax,max(dpinc[cx-2][cy],dpdec[cx-2][cy])+sum(cx-1,0,cy));
dpinc[cx][cy] = max(dpinc[cx][cy],cmax);
dpdec[cx][cy] = max(dpdec[cx][cy],cmax);
}
// skip two(ok)
if(cx == 2) continue;
long long two_empty = 0;
for(int py = 0;py < N;py++){
two_empty = max(two_empty,dpinc[cx-3][py]+sum(cx-2,0,py));
two_empty = max(two_empty,dpdec[cx-3][py]+sum(cx-2,0,py));
}
// cout << "!" << cx << ":" << two_empty << endl;
for(int cy = 0;cy < N;cy++){
dpinc[cx][cy] = max(dpinc[cx][cy],two_empty+sum(cx-1,0,cy));
dpdec[cx][cy] = max(dpdec[cx][cy],two_empty+sum(cx-1,0,cy));
}
}
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));
}
// cout << "===== dpinc =====" << endl;
// for(auto &i:dpinc){
// for(auto j:i) cout << j << " ";cout << endl;
// }
// cout << "===== dpdec =====" << endl;
// for(auto &i:dpdec){
// for(auto j:i) cout << j << " ";cout << endl;
// }
return ans;
}
