#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> a;
vector<vector<int>> fsh;
vector<vector<int>> prfx;
vector<vector<int>> possprfx;
vector<vector<vector<int>>> memo;
int N,M;
//x N possible
//last 2N possible negatif et pas negatif
//big 2 possible
int dp(int x, int last, int big){
if(memo[x][last+N][big]!=-1) return memo[x][last+N][big];
if(x==N) return 0;
int mx = 0;
for (auto i:fsh[x]) //O(N)
{
int c=0;
if(i==0){
if(last<=0) c=dp(x+1, 0, 1);
else if(last>0) c=dp(x+1,(-last), 1);
} else if(i>=abs(last)) {
if(big==0) break;
c=dp(x+1, i, 1);
}else if(i<abs(last)){
c=dp(x+1, i, 0);
}
if(x>0) {
if(last>=0) {
if(last<i&&i>0){
c+=prfx[x-1][i-1];
if(last>0) c-=prfx[x-1][last-1];
}
if(i<last&&last>0){
c+=prfx[x][last-1];
if(i>0) c-=prfx[x][i-1];
}
}else{
if(abs(last)<i&&i>0){
c+=prfx[x-1][i-1];
if(abs(last)>0) c-=prfx[x-1][abs(last)-1];
}
}
}
mx=max(c, mx);
}
return memo[x][last+N][big]=mx;
}
long long max_weights(signed n, signed m, std::vector<signed> X, std::vector<signed> Y, std::vector<signed> W) {
N=n; M=m;
fsh.resize(N+1, vector<int>(1,0));
prfx.resize(N+1, vector<int>(N+1,0));
possprfx.resize(N+1, vector<int>(N+1,0));
memo.resize(N+1, vector<vector<int>>(2*(N+1), vector<int>(2,-1)));
a.resize(N+1, vector<int>((N+1), 0));
for (int i = 0; i < M; i++){
a[X[i]][Y[i]] = W[i];
fsh[X[i]+1].push_back(Y[i]+1);
if(X[i]>0) fsh[X[i]-1].push_back(Y[i]+1);
}
for (int i = 0; i < N; i++) sort(fsh[i].begin(),fsh[i].end()); // N log N
for (int i = 0; i < N; i++) //N*N
{
for (int j = 0; j < N; j++)
{
prfx[i][j]=a[i][j];
if(j>0) prfx[i][j]+=prfx[i][j-1];
}
}
for (int i = 0; i <= N; i++) //N*N
{
int mxIndx=-1;
for (int j = 0; j < N; j++)
{
possprfx[i][j]=-a[i][j];
if(j>0) possprfx[i][j]+=possprfx[i][j-1];
if(i<N-1) possprfx[i][j]+=a[i+1][j];
if(mxIndx==-1 || possprfx[i][j]>possprfx[i][mxIndx]) mxIndx=j;
}
fsh[i].push_back(mxIndx+1);
for (int j = 0; j < N; j++) possprfx[i][j]=0;
mxIndx=-1;
for (int j = N-1; j >= 0; j--)
{
possprfx[i][j]=-a[i][j];
if(j>0) possprfx[i][j]+=possprfx[i][j-1];
if(i<N-1) possprfx[i][j]+=a[i+1][j];
if(mxIndx==-1 || possprfx[i][j]>possprfx[i][mxIndx]) mxIndx=j;
}
fsh[i].push_back(mxIndx+1);
}
int p=dp(0,0,1); //(N*2N*2*N) (300*600*300*2) (108.000.000)
return p;
}
