#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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 = 305;
bool fish[maxn][maxn];
map<basic_string<ll>, ll> weights;
ll dp[maxn][maxn][2][2];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
FOR(i,0,maxn){
FOR(j,0,maxn){
fish[i][j] = false;
dp[i][j][0][0] = 0;
dp[i][j][1][0] = 0;
dp[i][j][1][1] = 0;
dp[i][j][0][1] = 0;
}
}
FOR(i,0,M){
Y[i]++;
fish[X[i]][Y[i]] = 1;
weights[{X[i], Y[i]}] = W[i];
}
FOR(j,0,N){
FOR(i,0,N+1){
FOR(k,0,2){
FOR(l,0,2){
if (l==1 && k==0) continue;
ll temp = 0;
if (l==1){
if (dp[i][j][k][l] == 0) continue;
FOR(height, 0, N+1){
if (j>0 && fish[j-1][height] && i < height) temp += weights[{j-1, height}];
if (fish[j+1][height]) temp += weights[{j+1, height}];
dp[height][j+1][k][0] = max(dp[height][j+1][k][0], dp[i][j][k][l] + temp);
}
}else{
FOR(height, 0, N+1){
if (fish[j][height] && i >= height) temp -= weights[{j, height}];
if (k != 0 && j>0 && fish[j-1][height] && i < height) temp += weights[{j-1, height}];
if (fish[j+1][height]) temp += weights[{j+1, height}];
if (i != 0 && height==0){
dp[i][j+1][1][1] = max( dp[i][j+1][1][1], dp[i][j][k][l]+temp);
}
else if (height<i){
dp[height][j+1][0][0] = max(dp[height][j+1][0][0], dp[i][j][k][l]+temp);
}else if (height >= i) {
dp[height][j+1][1][0] = max(dp[height][j+1][1][0], dp[i][j][k][l]+temp);
}
}
}
}
}
}
}
ll ans = 0;
FOR(i,0,N) FOR(j,0,N+1) FOR(k,0,2) FOR(l,0,2){
ans = max(ans, dp[i][j][k][l]);
}
return ans;
}
