#include <bits/stdc++.h>
//#include "festival.h"
using namespace std;
long long fnd(vector <long long>& k, long long num){
long long l=0;
long long r=k.size()-1;
if (num >= k[r]) return r;
while (l<r) {
long long md=(l+r+1)/2;
if (k[md]<=num)
l=md;
else
r=md-1;
}
return l;
}
vector<int> max_coupons(int A,vector<int> P,vector <int> T){
vector <pair<long long,long long>> vp1;
vector <pair<long long,long long>> vp2;
vector <long long> psum1;
vector <long long> psum2;
long long sm1=0;
long long sm2=A;
vp1.push_back({0,-1});
vp2.push_back({0,-1});
for (long long i=0; i<P.size(); i++){
if (T[i]==1){
vp1.push_back({P[i],i});
}}
for (long long i=0; i<P.size(); i++){
if (T[i]==2){
vp2.push_back({P[i],i});
}}
sort(vp1.begin(),vp1.end());
sort(vp2.begin(),vp2.end());
for (long long i=0; i<vp1.size(); i++){
sm1+=vp1[i].first;
psum1.push_back(sm1);
}
for (long long i=0; i<vp2.size(); i++){
sm2-=vp2[i].first;
if (vp2[i].first==0){
psum2.push_back(sm2);
}
else if (sm2>=0){
sm2=sm2*2;
psum2.push_back(sm2);
}
else{
psum2.push_back(-1);
}
}
vector <int> ans;
for (long long i=1; i<vp2.size(); i++){
ans.push_back(vp2[i].second);
}
for (long long i=1; i<vp1.size(); i++){
ans.push_back(vp1[i].second);
}
return ans;
long long k=0,maxh=0,maxpos=-1;
for (long long i=0; i<vp2.size(); i++){
if (psum2[i]>=0){
long long kk=fnd(psum1,psum2[i]);
if (kk+i>=maxh){maxpos=i;maxh=kk+i;}
}}
for (long long i=1; i<=maxpos; i++){
ans.push_back(vp2[i].second);
}
for (long long i=1; i<=maxh-maxpos; i++){
ans.push_back(vp1[i].second);
}
/*
for (long long i=0; i<psum1.size(); i++){
cout<<psum1[i]<<' ';
}
cout<<"\n";
for (long long i=0; i<psum2.size(); i++){
cout<<psum2[i]<<' ';
}
cout<<"\n";
*/
return (ans);
}
