#include "fish.h"
#include <vector>
#include<algorithm>
using namespace std;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
bool flag = true;
for(auto it:X)
if(it%2)
{
flag = false;
break;
}
if(flag)
{
long long sol = 0;
for(auto it:W)
sol+=it;
return sol;
}
flag = true;
for(auto it:X)
if(it>1)
{
flag = false;
break;
}
if(flag)
{
std::vector<pair<int,int> > y0;
std::vector<pair<int,int> > y1;
int sz = X.size();
for(int i=0;i<M;i++)
if(X[i]==0) y0.emplace_back(Y[i],W[i]);
else y1.emplace_back(Y[i],W[i]);
std::sort(y0.begin(),y0.end());
std::sort(y1.begin(),y1.end());
if(N==2)
{
//efectiv...
long long sum0=0LL;
long long sum1=0LL;
for(auto it:y0)
sum0+=1LL*it.second;
for(auto it:y1)
sum1+=1LL*it.second;
return max(sum0,sum1);
}
long long sol = 0LL;
long long sum = 0LL;
for(auto it:y1)
sum += 1LL*it.second;
sol = sum;
/**
* Pana la un anumit punct luam din 0, apoi din 1
*/
int pnt0 = -1;
int pnt1 = 0;
long long sum0 = 0;
for(int i=0;i<(int)y0.size();i++)
{
pnt0++;
sum0 += 1LL * y0[i].second;
while(pnt1<(int)y1.size() && y1[pnt1].first<=y0[i].first)
{
sum -= 1LL * y1[pnt1].second;
pnt1++;
}
sol = max(sol,sum+sum0);
}
sol = max(sol,sum+sum0);
sum0 = 0LL;
for(auto it:y0)
sum0+=1LL*it.second;
sol = max(sol,sum0);
return sol;
}
flag = true;
for(auto it:Y)
if(it!=0)
{
flag = false;
break;
}
if(flag)
{
vector<vector<long long> > dp;
dp.resize(N+5);
for(int i = 0;i<N;i++)
dp[i].resize(2);
vector<int> repr;
repr.resize(N+5);
for(int i = 0;i<M;i++)
repr[X[i]] = W[i];
dp[1][0] = 0;
dp[1][1] = repr[0];
dp[1][2] = repr[1];
dp[1][3] = 0;
for(int i=2;i<N;i++)
{
dp[i][0] = max(max(dp[i-2][0],dp[i-2][2]),max(dp[i-2][1],dp[i-2][3])+1LL*repr[i-1]);
dp[i][1] = max(max(dp[i-2][0],dp[i-2][2])+1LL*repr[i-1],max(dp[i-2][1],dp[i-2][3])+1LL*repr[i-1]);
dp[i][2] = max(max(dp[i-2][0]+1LL*repr[i-2]+1LL*repr[i],dp[i-2][2]+1LL*repr[i]),max(dp[i-2][1]+1LL*repr[i],dp[i-2][3]+1LL*repr[i]));
dp[i][3] = max(max(dp[i-2][0]+1LL*repr[i-2],dp[i-2][2]),max(dp[i-2][1],dp[i-2][3]));
}
return max(max(dp[N-1][0],dp[N-1][1]),max(dp[N-1][2],dp[N-1][3]));
}
return 0;
}
