#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 ??
bool cmp1(pair<PLL,LL> a, pair<PLL,LL> b){
if (a.A.A!=b.A.A) return a.A.A<b.A.A;
return a.A.B<b.A.B;
}
bool cmp2(pair<PLL,LL> a, pair<PLL,LL> b){
if (a.A.A!=b.A.A) return a.A.A>b.A.A;
return a.A.B>b.A.B;
}
vector<int> max_coupons(int A, vector<int> p, vector<int> t){
int n=SZ(p);
int used[n];
memset(used,0,sizeof(used));
vector<int> ans;
LL a=(LL)A;
FOR(zzz,n){
vector<pair<PLL,LL> > gain, lose;
FOR(i,n){
if (used[i] || a<p[i]) continue;
LL d=a*(t[i]-1)-p[i]*t[i];
if (d>=0) gain.push_back(mp(mp(d,t[i]),i));
else lose.push_back(mp(mp(d+p[i],t[i]),i));
}
sort(gain.begin(),gain.end(),cmp1);
sort(lose.begin(),lose.end(),cmp2);
if (!gain.empty()){
LL x=gain[0].A.A, id=gain[0].B;
a+=x;
ans.push_back(id);
used[id]=1;
//cout<<id<<": "<<a<<" "<<x<<"\n";
}
else if (!lose.empty()){
LL x=lose[0].A.A, id=lose[0].B;
x-=p[id];
a+=x;
ans.push_back(id);
used[id]=1;
//cout<<id<<": "<<a<<" "<<x<<"\n";
}
else break;
}
return ans;
}
