#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define f0(i, n) for(int i = 0; i < (n); i++)
#define f1(i, n) for(int i = 1; i <= (n); i++)
#define pb push_back
#define ff first
#define ss second
typedef vector<int> vi;
typedef long long ll;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
bool allxeven = true;
bool allxleq1 = true;
bool ally0 = true;
f0(i, M) {
if(X[i] % 2 == 1) allxeven = false;
if(X[i] > 1) allxleq1 = false;
if(Y[i] != 0) ally0 = false;
}
if (allxeven) {
ll ret = 0;
f0(i, M) ret += W[i];
return ret;
}
if(allxleq1) {
ll ret = 0;
ll ans = 0;
int arr[N][2];
f0(i, N) arr[i][0] = 0, arr[i][1] = 0;
f0(i, M) {
arr[X[i]][Y[i]] = W[i];
}
f0(i, N) {
ans += arr[i][1];
}
ret = ans;
f0(i, N) {
ans -= arr[i][1];
ans += arr[i][0];
ret = max(ret, ans);
}
return ret;
}
if(ally0) {
int arr[N];
f0(i, N) arr[i] = 0;
f0(i, M) arr[X[i]] = W[i];
ll dp[N][4];
dp[0][0] = -1e18;
dp[0][1] = -1e18;
dp[0][2] = 0;
dp[0][3] = arr[0];
dp[1][0] = 0;
dp[1][1] = arr[1];
dp[1][2] = arr[0];
dp[1][3] = -1e18;
f1(i, N-2) {
dp[i+1][0] = max(dp[i][0], dp[i][2]);
dp[i+1][1] = max(dp[i][0], dp[i][2]) + arr[i+1];
dp[i+1][2] = max(dp[i][1], dp[i][3]);
dp[i+1][3] = dp[i][1] + arr[i+1];
}
return max({
dp[N-1][0],
dp[N-1][1],
dp[N-1][2]
});
}
return 0;
}
