#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;
vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
int n = p.size();
vector<pii>one, two;
for(int i=0; i<n; i++){
if(t[i] == 1) one.pb({p[i],i});
else two.pb({p[i],i});
}
sort(one.begin(), one.end());
sort(two.begin(), two.end());
int k1 = one.size(), k2 = two.size();
vector<int> psum;
psum.pb(one[0].fi);
for(int i=1; i<k1; i++) psum.pb(psum[i-1] + one[i].fi);
int money = a;
int ans = 0, num = -1;
for(int i=0; i<k2; i++){
if(money < two[i].fi) break;
money -= two[i].fi;
money *= 2;
int x = upper_bound(psum.begin(), psum.end(), money) - psum.begin();
if(i+1+x > ans){
ans = i+1+x;
num = i;
}
}
vector<int> res;
if(num != -1){
money = a;
for(int i=0; i<=num; i++){
res.pb(two[i].se);
money -= two[i].fi;
money *= 2;
}
int x = upper_bound(psum.begin(), psum.end(), money) - psum.begin();
for(int i=0; i<x; i++){
res.pb(one[i].se);
}
}
return res;
}
