#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
const ll maxn = 100005;
unordered_set<ll> fish[maxn];
map<basic_string<ll>, ll> weights;
ll dp[6][6][maxn];
unordered_set<ll> temppos[maxn];
basic_string<ll> possibles[maxn];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
FOR(i,0,6){
FOR(j,0,6){
FOR(k,0,maxn){
dp[i][j][k] = 0;
}
}
}
FOR(i,0,maxn) temppos[i].insert(0);
FOR(i,0,M){
Y[i]++;
fish[X[i]].insert(Y[i]);
weights[{X[i], Y[i]}] = W[i];
if (X[i] > 0) temppos[X[i]-1].insert(Y[i]);
temppos[X[i]+1].insert(Y[i]);
}
FOR(i,0,maxn){
for (auto&k : temppos[i]) possibles[i].push_back(k);
}
FOR(i,0,maxn) sort(possibles[i].begin(), possibles[i].end());
FOR(k,0,N){
FOR(X,0,6){
FOR(Y,0,6){
ll i=0,j=0;
if (k>=2 && possibles[k-2].size() <= X) continue;
else if (k>=2) i = possibles[k-2][X];
if (k>=1 && possibles[k-1].size() <= Y) continue;
else if (k>=1) j = possibles[k-1][Y];
ll temp = 0;
set<ll> visited;
FOR(Z, 0, 6){
if (possibles[k].size() <= Z) continue;
ll height = possibles[k][Z];
if (fish[k+1].count(height)) temp += weights[{k+1, height}];
for (auto&p : fish[k]){
if (visited.count(p)==0 && j >= p && p<=height){
temp -= weights[{k, p}];
visited.insert(p);
}
}
if (k>0 && fish[k-1].count(height) && i < height && j<height) temp += weights[{k-1, height}];
dp[Y][Z][k+1] = max(dp[Y][Z][k+1], dp[X][Y][k] + temp);
}
}
}
}
ll ans = 0;
FOR(i,0,6){
FOR(j,0,6){
FOR(k,0,N+1){
ans = max(ans, dp[i][j][k]);
//if (dp[i][j][k]==11) cout << i << " " << j << " " << k << endl;
}
}
}
return ans;
}
