#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*2;
const ll MOD = 1e9+7;
const ll INF = 1e15;
struct Coupon {
ll p, t, n;
bool operator < (const Coupon& x) const {
if((t==1)^(x.t==1)) return x.t==1;
if(t==1) return p<x.p;
return p*t*(x.t-1) < x.p*x.t*(t-1);
}
} arr[MAXN];
vector<int> lst[5];
const int MAXM = 20;
ll dp[MAXM][MAXM][MAXM][MAXM];
vector<int> pv[MAXM][MAXM][MAXM][MAXM];
vector<int> res, res1;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int n = P.size();
for(int i=0; i<n; i++) arr[i] = {P[i],T[i], i};
sort(arr, arr+n);//for(int i=0;i<n;i++)cout<<arr[i].n<<bl;cout<<endl;
int idx=0; ll cur=A;
while(idx<n && cur<INF) {
if((cur-arr[idx].p)*arr[idx].t < cur) break;
res.push_back(arr[idx].n);
cur = arr[idx].t*(cur-arr[idx].p); idx++;
}
if(cur>=INF) {
while(idx<n) res.push_back(arr[idx++].n);
return res;
}
for(int t=1;t<=4;t++) lst[t] = {-1};
for(int i=idx;i<n;i++) {
lst[arr[i].t].push_back(i);
}
pair<int, vector<int> > mx = make_pair(0, vector<int>{0});
for(int i=0;i<MAXM&&i<lst[1].size();i++) {
for(int j=0;j<MAXM&&j<lst[2].size();j++) {
for(int k=0;k<MAXM&&k<lst[3].size();k++) {
for(int l=0;l<MAXM&&l<lst[4].size();l++) {
if(!i && !j && !k && !l) {
dp[i][j][k][l] = cur;
} else {
int x = max(max(lst[1][i], lst[2][j]), max(lst[3][k], lst[4][l]));
int di = (lst[1][i]==x);
int dj = (lst[2][j]==x);
int dk = (lst[3][k]==x);
int dl = (lst[4][l]==x);
if(dp[i-di][j-dj][k-dk][l-dl] >= arr[x].p) {
ll tmp = arr[x].t*(dp[i-di][j-dj][k-dk][l-dl]-arr[x].p);
if(dp[i][j][k][l] <= tmp) {
dp[i][j][k][l] = tmp;
pv[i][j][k][l] = {i-di, j-dj, k-dk, l-dl};
} mx = max(mx, make_pair(i+j+k+l, vector<int>{i,j,k,l}));
}
}
}
}
}
}
if(mx.ff == 0) return res;
vector<int> v = mx.ss;
while(v[0]+v[1]+v[2]+v[3]) {//for(int x:v)cout<<x<<bl;cout<<endl;cout.flush();
int x=0;
for(int t=1;t<=4;t++) x=max(x, lst[t][v[t-1]]);
res1.push_back(arr[x].n);
v = pv[v[0]][v[1]][v[2]][v[3]];
}
reverse(all(res1)); for(int x:res1) res.push_back(x);
return res;
}
