#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
const ll INF = 1e17;
pll f(pll x) {
if (x.nd == 2ll) {
return {x.st, 1};
}
if (x.nd == 3ll) {
return {x.st * 3ll, 4ll};
}
return {x.st * 2ll, 3ll};
}
bool por(pair<pll, int> a, pair<pll, int> b) {
pll x = f(a.st);
pll y = f(b.st);
return ((x.st * y.nd) < (y.st * x.nd));
}
std::vector<int> max_coupons(int A, std::vector<int> P1, std::vector<int> T1) {
int n2 = P1.size();
vector<pair<pll, int>> T;
vector<pair<ll, int>> pom;
rep(i, n2) {
if (T1[i] == 1) {
pom.pb({P1[i], i});
}
else {
T.pb({{P1[i], T1[i]}, i});
}
}
int n = T.size();
sort(all(T), por);
sort(all(pom));
vector<int> ans;
bool dodan[n2];
rep(i, n2) {
dodan[i] = false;
}
ll val = A;
rep(i, n) {
if (val >= INF) {
for (auto x: ans) {
dodan[x] = true;
}
rep(j, n2) {
if (dodan[j]) continue;
ans.pb(j);
}
return ans;
}
if (val >= T[i].st.st) {
val = (val - T[i].st.st) * T[i].st.nd;
ans.pb(T[i].nd);
}
}
for (auto p: pom) {
if (val >= p.st) {
val -= p.st;
ans.pb(p.nd);
}
}
return ans;
}
