#include "fish.h"
using namespace std;
#include<bits/stdc++.h>
#define ll long long
long long subtask1(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W){
long long ans=0;
for(int i=0; i<M; i++){
ans+=W[i];
}
return ans;
}
long long subtask2(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W){
vector<pair<int,int>> c0;
vector<pair<int,int>> c1;
long long sum0=0;
long long sum1=0;
for(int i=0; i<M; i++){
if(X[i]==0){
c0.push_back({Y[i], W[i]});
sum0+=W[i];
}
else{
c1.push_back({Y[i], W[i]});
sum1+=W[i];
}
}
if(N==2){
return max(sum0, sum1);
}
sort(c1.begin(), c1.end());
sort(c0.begin(), c0.end());
long long ans=max(sum0, sum1);
long long mom=sum1;
int j=0;
for(int i=0; i<(int)c1.size(); i++){
while(j<(int)c0.size() && c0[j].first<c1[i].first){
mom+=c0[j].second;
j++;
}
ans=max(ans, mom);
mom-=c1[i].second;
}
return ans;
}
long long gain(int h1, int free1, int h2, int free2, vector<pair<int,int> >& c1, vector<pair<int,int> >& c2){
//wand von 1 ist grösser
int wallh=c1[h1].first;
ll ans=0;
for(int i=max(h2, (int)c2.size()-free2); i<(int)c2.size(); i++){
if(c2[i].first < wallh){
ans+= c2[i].second;
}
}
return ans;
}
const int INF=1e9+7;
long long subtask3(int n, int m, vector<int> x, vector<int> y, vector<int> w){
vector<int> weight(n);
for(int i=0; i<m; i++){
weight[x[i]]=w[i];
}
vector<long long > dp(n+1, 0);
for(int i=0; i<=n; i++){
dp[i] = dp[i-1];
if(0<=i-2){
dp[i] = max(dp[i], dp[i-2] + max(weight[i-1], weight[i-2]));
}
}
return dp[n];
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
if(N==1) return 0;
bool sub1=true;
bool sub2=true;
bool sub3=true;
for(int i=0; i<M; i++){
if(X[i]%2==1){
sub1=false;
}
if(X[i]>1){
sub2=false;
}
if(Y[i]!=0){
sub3=false;
}
}
if(sub1){
return subtask1(N, M, X, Y, W);
}
if(sub2){
return subtask2(N, M, X, Y, W);
}
if(sub3){
return subtask3(N, M, X, Y, W);
}
}
