#include <bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int MAXN = 1e5 + 5;
ll sum_tutto(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
ll sum = 0;
for (auto x : W) sum += x;
return sum;
}
ll res_minore_di_due(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
if (N == 2) {
// massimo tra 0 e 1
ll one = 0;
ll zero = 0;
for (int i = 0; i < M; i ++) {
if (X[i] == 0) zero += W[i];
else one += W[i];
}
return max(one, zero);
}
// altrimenti piazza una riga in 2 e poi prendi prefisso maggiore piazzando in 1
ll sum = 0;
for (int i = 0; i < M; i ++) {
if (X[i] == 1) sum += W[i];
}
vector<vector<ll>> pos(2, vector<ll>(N + 5, 0));
for (int i = 0; i < M; i ++) {
pos[X[i]][Y[i]] += W[i];
}
ll best_res = sum;
ll sum_zero = 0;
ll sum_uno = 0;
for (int i = 0; i < N + 5; i ++) {
sum_zero += pos[0][i];
sum_uno += pos[1][i];
best_res = max(best_res, sum - sum_uno + sum_zero);
}
return best_res;
}
ll res_y_zero(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<ll>> dp(2, vector<ll>(N + 5)); // posso prendere a sx o no, posizione
vector<ll> grid(N + 5);
for (int i = 0; i < M; i ++) grid[X[i]] = W[i];
for (int i = N; i >= 0; i --) {
dp[0][i] = dp[1][i + 1];
dp[0][i] = max(dp[0][i], dp[0][i + 1]);
dp[0][i] = max(dp[0][i], dp[0][i + 2] + grid[i + 1]);
dp[0][i] = max(dp[0][i], dp[1][i + 3] + grid[i + 1]);
dp[0][i] = max(dp[0][i], dp[0][i + 3] + grid[i + 1]);
if (i != 0) {
dp[1][i] = dp[1][i + 1];
dp[1][i] = max(dp[1][i], dp[0][i + 1] + grid[i - 1]);
dp[1][i] = max(dp[1][i], dp[0][i + 2] + grid[i - 1] + grid[i + 1]);
dp[1][i] = max(dp[1][i], dp[1][i + 3] + grid[i - 1] + grid[i + 1]);
dp[1][i] = max(dp[1][i], dp[0][i + 3] + grid[i - 1] + grid[i + 1]);
}
}
ll best_res = 0;
for (int i = 0; i <= N; i ++) {
best_res = max(best_res, dp[0][i]);
best_res = max(best_res, dp[1][i]);
}
return best_res;
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
bool all_even = 1;
for (auto x : X) if (x % 2) all_even = 0;
if (all_even) return sum_tutto(N, M, X, Y, W);
bool minore_di_due = 1;
for (auto x : X) if (x >= 2) minore_di_due = 0;
if (minore_di_due) return res_minore_di_due(N, M, X, Y, W);
bool y_zero = 1;
for (auto y : Y) if (y >= 0) minore_di_due = 0;
return res_y_zero(N, M, X, Y, W);
}
