#include "festival.h"
#include <cassert>
#include <cstdio>
#include "festival.h"
using namespace std;
#include<algorithm>
#define ll long long
#define vll vector<ll>
int n;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
vector<int> ind;
n = P.size();
for(int i = 0; i < n; i++)ind.push_back(i);
auto val = [&](int i, ll x){
return max((ll)-1,(x-P[i])*T[i]);
};
sort(ind.begin(), ind.end(), [&](int i, int j){
return val(i,val(j,0)) < val(j,val(i,0));
});
ll cur = A;
vector<int> ans;
int i = 0;
for(; i < n; i++){
if(val(ind[i],cur) >= cur){
ans.push_back(ind[i]);
cur = val(ind[i],cur);
if(cur > 1e15){
for(int j = i+1; j < n; j++)ans.push_back(ind[j]);
return ans;
}
}else break;
}
vector<int> his[5];
for(; i < n; i++){
if(T[ind[i]] == 1 || his[T[ind[i]]].size() <= 30)his[T[ind[i]]].push_back(ind[i]);
}
sort(his[1].begin(), his[1].end(), [&](int i, int j){
return P[i] < P[j];
});
vll s(his[1].size()+1, 0);
for(int i = 0; i < his[1].size(); i++)s[i+1] = s[i]+P[his[1][i]];
vll maxi = {0,0,0,0};
vector<int> add;
for( i = 0; i <= his[2].size(); i++){
for(int j = 0; j <= his[3].size(); j++){
for(int k = 0; k <= his[4].size(); k++){
ll curcur = cur;
vector<int> v;
for(int t = 0; t < i; t++)v.push_back(his[2][t]);
for(int t = 0; t < j; t++)v.push_back(his[3][t]);
for(int t = 0; t < k; t++)v.push_back(his[4][t]);
sort(v.begin(), v.end(), [&](int i, int j){
return val(i,val(j,cur)) < val(j,val(i,cur));
});
for(auto x : v){
curcur = val(x, curcur);
if(curcur < 0)break;
}
if(curcur < 0)continue;
int pos = upper_bound(s.begin(), s.end(), curcur)-s.begin()-1;
if(pos+i+j+k > maxi[0]+maxi[1]+maxi[2]+maxi[3]){
maxi = {pos, i, j, k};
add = v;
}
}
}
}
for(int a : add)ans.push_back(a);
for( i = 0; i < maxi[0]; i++)ans.push_back(his[1][i]);
return ans;
}
/*
int main() {
int N, A;
assert(2 == scanf("%d %d", &N, &A));
std::vector<int> P(N), T(N);
for (int i = 0; i < N; i++)
assert(2 == scanf("%d %d", &P[i], &T[i]));
fclose(stdin);
std::vector<int> R = max_coupons(A, P, T);
int S = R.size();
printf("%d\n", S);
for (int i = 0; i < S; i++)
printf("%s%d", (i == 0 ? "" : " "), R[i]);
printf("\n");
fclose(stdout);
return 0;
}*/
