#include "festival.h"
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;
//if can gain, always take the one with smallest gain
//else take the one with smallest loss
//we must keep gaining then losing ??
vector<int> max_coupons(int A, vector<int> p, vector<int> t){
int n=SZ(p);
vector<PLL> v1,v2;
FOR(i,n){
if (t[i]==2) v2.push_back(mp(p[i],i));
else v1.push_back(mp(p[i],i));
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
LL m=SZ(v1);
vector<LL> pref(m+1,0);
FOR(i,m) pref[i+1]=pref[i]+v1[i].A;
LL a=(LL)A;
LL mx=upper_bound(pref.begin(),pref.end(),a)-pref.begin()-1, id=0;
FR(i,1,SZ(v2)+1){
LL x=v2[i-1].A;
if (a<x) break;
a=(a-x)*2;
LL tmp=upper_bound(pref.begin(),pref.end(),a)-pref.begin()-1+i;
if (tmp>mx){
mx=tmp;
id=i;
}
}
vector<int> ans;
FOR(i,id) ans.push_back((int)v2[i].B);
FOR(i,mx-id) ans.push_back((int)v1[i].B);
return ans;
}
