#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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<signed> max_coupons(signed a, vector<signed> p, vector<signed> 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;
if(k1){
psum.pb(one[0].fi);
for(int i=1; i<k1; i++) psum.pb(psum[i-1] + one[i].fi);
}
int money = a;
int x = upper_bound(psum.begin(), psum.end(), money) - psum.begin();
int ans = x, num = -1;
int f=0, ff=-1;
for(int i=0; i<k2; i++){
if(money < two[i].fi) break;
money -= two[i].fi;
money *= 2;
x = upper_bound(psum.begin(), psum.end(), money) - psum.begin();
if(i+1+x > ans){
ans = i+1+x;
num = i;
}
if(money > n*(1e9)){
f = 1;
ff = i;
break;
}
}
vector<signed> res;
if(f){
set<int>s;
for(int i=0; i<n; i++) s.insert(i);
for(int i=0; i<=ff; i++){
res.pb(two[i].se);
s.erase(two[i].se);
}
for(auto i:s) res.pb(i);
return res;
}
if(num == -1){
for(int i=0; i<ans; i++){
res.pb(one[i].se);
}
} else {
money = a;
for(int i=0; i<=num; i++){
res.pb(two[i].se);
money -= two[i].fi;
money *= 2;
}
x = upper_bound(psum.begin(), psum.end(), money) - psum.begin();
for(int i=0; i<x; i++){
res.pb(one[i].se);
}
}
return res;
}
