#include "fish.h"
#include<bits/stdc++.h>
#include<iostream>
#include<math.h>
#include <vector>
#define FOR(i,a,b) for(int i = a; i < b; i++)
typedef long long ll;
using namespace std;
ll sub1(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
return accumulate(W.begin(), W.end(), 0LL);
}
ll sub2(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
ll ans = 0;
vector<ll>cs1(N + 1, 0), cs2(N + 1, 0);
for (int i = 0; i < M; i++) {
if (X[i] == 0)
cs1[Y[i]] += W[i];
else
cs2[Y[i]] += W[i];
}
for (int i = 1; i < N; i++)
cs1[i] += cs1[i - 1], cs2[i] += cs2[i - 1];
ans = max(cs1[N - 1], cs2[N - 1]);
if (N == 2) return ans;
for (int i = 0; i < N; i++) {
ll cur = cs2[N - 1];
cur -= cs2[i];
cur += cs1[i];
ans = max(ans, cur);
}
return ans;
}
ll sub3(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
vector<ll> A(N);
FOR(i, 0, M) {
A[X[i]] = W[i];
}
ll dp[N][2]; memset(dp, 0, sizeof(dp));
if (N > 1) {
dp[1][0] = A[1];
dp[1][1] = A[0];
}
FOR(i, 2, N) {
dp[i][0] = dp[i - 1][1] + A[i];
dp[i][1] = max(max(dp[i - 1][1], dp[i - 1][0]), dp[i - 2][0] + A[i - 1]);
}
FOR(i, 0, M) {
if (Y[i] > 0) {
ll ans = 0; FOR(j, 0, M) ans += W[j];
return ans;
}
}
return max(dp[N - 1][0], dp[N - 1][1]);
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
bool sb1 = true, sb2 = true, sb3 = true;
for (int i = 0; i < M; i++) {
if (X[i] % 2 == 1) sb1 = false;
if (X[i] >= 2) sb2 = false;
if (Y[i] != 0) sb3 = false;
}
if (sb1) return sub1(N, M, X, Y, W);
else if(sb2) return sub2(N, M, X, Y, W);
else if(sub3) return sub3(N, M, X, Y, W);
}
