#include "fish.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include "fish.h"
#include <cassert>
#include <cstdio>
// BEGIN SECRET
#include <string>
// END SECRET
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> V;
struct info{
int y;
int w;
int flag;
};
struct CustomCompare
{
bool operator()(info const& p, info const& p1)
{
return (p.y > p1.y) || (p.y == p1.y && p.flag > p1.flag);
}
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){
// se X[i] è pari, allora posso ergere ponti per prendere tutti
bool subtask1 = true;
bool subtask2 = true;
bool subtask3 = true;
bool subtask4 = true;
long long ans = 0;
// for(int i = 0; i < (int)X.size(); i++)
// V[X[i]][Y[i]] = W[i];
for(int i = 0; i < (int)X.size(); i++){
subtask1 &= X[i] % 2 == 0;
subtask2 &= X[i] <= 1;
subtask3 &= Y[i] == 0;
subtask4 &= N <= 300;
}
if(subtask1){
ans = accumulate(W.begin(), W.end(), 0L);
return ans;
}
if(subtask2){
if(N == 1) return 0;
if(N == 2){
long long x0 = 0, x1 = 0;
for(int i = 0; i < (int)X.size(); i++){
if(X[i] == 1) x1 += W[i];
else x0 += W[i];
}
return max(x1, x0);
}
priority_queue<info, vector<info>, CustomCompare> pq;
long long x1 = 0;
for(int i = 0; i < (int)X.size(); i++){
pq.push({Y[i], W[i], X[i] == 0});
if(X[i] == 1) x1 += W[i];
}
long long curr = x1;
ans = curr;
while(!pq.empty()){
info p = pq.top();
pq.pop();
if(p.flag) curr += p.w, ans = max(ans, curr);
else curr -= p.w;
}
return ans;
}
if(subtask3){
long long dp[M][3];
for(int i = 0; i < M; i++)
for(int j = 0; j < 3; j++) dp[i][j] = 0;
vector<pair<int, int>> V;
for(int i = 0; i < M; i++) V.push_back({X[i], W[i]});
sort(V.begin(), V.end());
dp[0][0] = V[0].second;
if(V[0].first != 0) {
dp[0][1] = V[0].second;
}
dp[0][2] = max(dp[0][1], dp[0][0]);
for(int i = 1; i < M; i++){
if(abs(V[i].first-V[i-1].first) == 1){
if(V[i].first < N-1)
dp[i][0] = dp[i-1][1]+V[i].second;
if(i >= 2){
dp[i][1] = dp[i-2][2] + V[i].second;
}else dp[i][1] = V[i].second;
dp[i][2] = max(dp[i-1][2], max(dp[i][0], dp[i][1]));
}else{
dp[i][1] = dp[i][2] = dp[i-1][2] + V[i].second;
if(V[i].first < N-1)
dp[i][0] = dp[i][1];
}
}
return dp[M-1][2];
}
if(subtask4){
long long mat[N][N];
long long pref[N][N][2];
long long suff[N][N][2];
long long memo[N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
pref[i][j][0] = 0;
pref[i][j][1] = 0;
suff[i][j][0] = 0;
suff[i][j][1] = 0;
mat[i][j] = 0;
}
memo[i] = 0;
}
for(int i = 0; i < M; i++) mat[N-Y[i]-1][X[i]] = W[i];
long long sum = 0;
for(int i = N-1; i >= 0; i--){
sum += mat[i][0];
pref[i][0][0] = sum;
memo[0] = max({memo[0], pref[i][0][0]});
}
sum = 0;
for(int i = 0; i < N; i++){
sum += mat[i][0];
suff[i][0][0] = sum;
memo[0] = max({memo[0], suff[i][0][0]});
}
for(int j = 1; j < N; j++){
sum = 0;
// popoliamo pref
for(int i = N-1; i >= 0; i--){
// il prefisso lo posso combinare con il prefisso della colonna precedente
// o con il suffisso della colonna precedente, ma entrambi applicando la colonna a sinistra
sum += mat[i][j];
for(int k = 0; k < N; k++){
if(j < N-1){
pref[i][j][0] = max(pref[i][j][0], pref[k][j-1][1] + sum);
pref[i][j][0] = max(pref[i][j][0], suff[k][j-1][1] + sum);
}
if(k < i)
pref[i][j][1] = max(pref[i][j][1], suff[k][j-1][1] + sum);
}
if(j >= 2){
if(j < N-1)
pref[i][j][0] = max(pref[i][j][0], memo[j-2] + sum);
pref[i][j][1] = max(pref[i][j][1], memo[j-2] + sum);
}
memo[j] = max({memo[j], memo[j-1], max(pref[i][j][0], pref[i][j][1])});
}
// adesso dobbiamo popolare suff qui i cazzi sono peggiori
sum = 0;
for(int i = 0; i < N; i++){
sum += mat[i][j];
for(int k = 0; k < N; k++){
if(j < N-1){
suff[i][j][0] = max(suff[i][j][0], pref[k][j-1][1] + sum);
suff[i][j][0] = max(suff[i][j][0], suff[k][j-1][1] + sum);
}
if(k > i && j < N-1){
suff[i][j][0] = max(suff[i][j][0], pref[k][j-1][0] + sum);
}
suff[i][j][1] = max(suff[i][j][1], sum);
if(j >= 2)
suff[i][j][1] = max(suff[i][j][1], memo[j-2] + sum);
}
if(j >= 2){
if(j < N-1)
suff[i][j][0] = max(suff[i][j][0], memo[j-2] + sum);
suff[i][j][1] = max(suff[i][j][1], memo[j-2] + sum);
}
memo[j] = max({memo[j], memo[j-1], max(suff[i][j][0], suff[i][j][1])});
}
}
return memo[N-1];
}
return ans;
}
