#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
int n, m;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N; m = M;
bool f = true, s = true, t = true;
for(int i = 0; i < m; i++) {
if(X[i] & 1) f = false;
if(X[i] > 1) s = false;
if(Y[i] != 0) t = false;
}
if(f) {
ll ans = 0;
for(int i = 0; i < m; i++) ans += W[i];
return ans;
}
if(s) {
ll f1 = 0, s1 = 0;
vector<ll> pref(n+1);
for(int i = 0; i < m; i++) {
if(X[i] == 0) f1 += W[i];
else s1 += W[i];
}
vector<array<ll, 2>> v;
for(int i = 0; i < m; i++) {
if(X[i] == 0) {
pref[Y[i]] += W[i];
}
else {
v.push_back({Y[i], W[i]});
}
}
if(n <= 2) return max(f1, s1);
sort(v.begin(), v.end());
for(int i = 1; i <= n; i++) pref[i] += pref[i-1];
ll curr = s1; ll ans = s1;
for(auto [y, w] : v) {
ans = max(ans, curr+pref[y-1]);
curr -= w;
ans = max(ans, curr+pref[y]);
}
return max(ans, f1);
}
if(t) {
vector<array<ll, 2>> dp(m, {0, 0});
dp[0][0] = W[0];
for(int i = 1; i < m; i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + W[i]);
dp[i][1] = W[i-1];
if(i >= 2) {
dp[i][1] = max({dp[i][1], dp[i-2][0]+W[i-1], dp[i-2][1]+W[i-1]});
}
}
return max(dp[m-1][0], dp[m-1][1]);
}
}
/*int main()
{
cout << max_weights(5, 4, {0, 1, 0, 1}, {2, 1, 4, 3}, {5, 2, 1, 3});
}*/
