#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 3e15;
int tk;
struct coupon{
int p, t, idx;
void apply(){
tk -= p; tk *= t;
if (tk > INF) tk = INF;
if (tk < 0) tk = -1;
}
};
vector<signed> max_coupons(signed A, vector<signed> P, vector<signed> T) {
int n = P.size();
vector<coupon> twos, ones;
for (int i=0; i<n; i++) {
if (T[i] == 2) twos.push_back({P[i], T[i], i});
else ones.push_back({P[i], T[i], i});
}
sort(twos.begin(), twos.end(), [](coupon &a, coupon &b){return a.p < b.p;});
sort(ones.begin(), ones.end(), [](coupon &a, coupon &b){return a.p < b.p;});
vector<int> pr = {0};
for (auto [p, t, idx]: ones) pr.push_back(pr.back() + p);
tk = A;
int mx = 0, m2 = 0;
for (int i=0; i<twos.size(); i++){
twos[i].apply();
if (tk < 0) break;
int l = 0, r = pr.size() - 1;
while (l<r){
int m = (l+r+1)/2;
if (pr[m] <= tk) l = m; else r = m-1;
}
if (i + 1 + l > mx) mx = i+1+l, m2 = i+1;
}
tk = A;
vector<signed> ans;
for (int i=0; i<m2; i++) ans.push_back(twos[i].idx), twos[i].apply();
for (int i=0; i<ones.size(); i++) if (tk >= ones[i].p) ones[i].apply(), ans.push_back(ones[i].idx); else break;
return ans;
}
