#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
int offset = 3;
int rightOff = 3;
vector<vector<ll>> grid(N + offset + rightOff, vector<ll>(N)), prefix(N + offset + rightOff, vector<ll>(N));
vector<vector<vector<ll>>> dp(N + offset + rightOff, vector<vector<ll>>(N, vector<ll>(3)));
// dp[x][y][0] = includex mid, right
// [1] = excluded right
// [2] = excluded mid & right
for(int i = 0; i < M; i++){
grid[offset + X[i]][Y[i]] = W[i];
}
// Create prefix sums:
for(int x = offset; x < N + offset; x++){
prefix[x][0] = grid[x][0];
for(int y = 1; y < N; y++){
prefix[x][y] = prefix[x][y - 1] + grid[x][y];
}
}
// calc dp
for(int xF = 0; xF < N; xF++){
int x = xF + offset;
for(int y = 0; y < N; y++){
for(int h = 0; h < N; h++){
// dp[i] = dp[i - 3]
dp[x][y][0] = max(
dp[x][y][0],
dp[x - 3][h][0] + prefix[x - 1][y] + prefix[x + 1][y]
);
dp[x][y][1] = max(
dp[x][y][1],
dp[x - 3][h][0] + prefix[x - 1][y]
);
dp[x][y][2] = max(
dp[x][y][2],
dp[x - 3][h][0] + prefix[x - 1][y]
);
// dp[i] = dp[i - 2]
if(x >= offset + 2){
dp[x][y][0] = max(
dp[x][y][0],
dp[x - 2][h][1] + prefix[x + 1][y] + prefix[x - 1][max(y, h)]
);
dp[x][y][1] = max(
dp[x][y][1],
dp[x - 2][h][1] + prefix[x - 1][max(y, h)]
);
dp[x][y][2] = max(
dp[x][y][2],
dp[x - 2][h][1] + prefix[x - 1][max(y, h)]
);
}
// dp[i] = dp[i - 1]
ll additional = 0;
ll excludedMid = 1;
if(x >= offset + 1){
if(y > h){
additional = prefix[x - 1][y] - prefix[x - 1][h];
}else if(h > y){
additional = prefix[x][h] - prefix[x][y];
excludedMid = 0;
}
assert(additional >= 0);
dp[x][y][0] = max({
dp[x][y][0],
dp[x - 1][h][0] - prefix[x][y] + prefix[x + 1][y],
// dp[x - 1][h][0],
// dp[x - 1][h][0],
// dp[x - 1][h][1] + prefix[x + 1][y],
dp[x - 1][h][2] + additional + prefix[x + 1][y]
});
dp[x][y][1] = max({
dp[x][y][1],
// dp[x - 1][h][0], // <-- might want to add again (only here)
dp[x - 1][h][2] + additional
});
dp[x][y][2] = max({
dp[x][y][2],
// dp[x - 1][h][1],
dp[x - 1][h][2] + additional * excludedMid
});
}
// cout << "new\n";
}
}
}
ll best = 0;
for(int x = 0; x < N; x++){
for(int y = 0; y < N; y++){
best = max({
best,
dp[offset + x][y][0],
dp[offset + x][y][1],
dp[offset + x][y][2],
});
}
}
return best;
}
// #include "grader.cpp"
