#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
if (hash1 != hash2) {
return hash1 ^ hash2;
}
// If hash1 == hash2, their XOR is zero.
return hash1;
}
};
unordered_map<pair<int,int>, int, hash_pair> a;
vector<vector<int>> fsh;
vector<vector<int>> prfx;
map<pair<int,pair<int,int>>, 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.find({x,{last,big}})!=memo.end()) return memo[{x,{last,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,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));
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];
}
}
int p=dp(0,0,1); //(N*2N*2*N) (300*600*300*2) (108.000.000)
return p;
}
