#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
using ll = long long;
const int n = (int)P.size();
// Buckets by multiplier. Keep (price, index), and sort ascending by price.
vector<pair<ll,int>> b2, b3, b4, b1;
b2.reserve(n); b3.reserve(n); b4.reserve(n); b1.reserve(n);
for (int i = 0; i < n; ++i) {
if (T[i] <= 1) b1.emplace_back((ll)P[i], i);
else if (T[i] == 2) b2.emplace_back((ll)P[i], i);
else if (T[i] == 3) b3.emplace_back((ll)P[i], i);
else b4.emplace_back((ll)P[i], i); // treat T>=4 as 4
}
auto by_price = [](const pair<ll,int>& a, const pair<ll,int>& b){
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
};
sort(b1.begin(), b1.end(), by_price);
sort(b2.begin(), b2.end(), by_price);
sort(b3.begin(), b3.end(), by_price);
sort(b4.begin(), b4.end(), by_price);
// Pointers to the next cheapest in each T>=2 bucket
size_t i2 = 0, i3 = 0, i4 = 0;
auto has2 = [&]{ return i2 < b2.size(); };
auto has3 = [&]{ return i3 < b3.size(); };
auto has4 = [&]{ return i4 < b4.size(); };
auto cdiv = [](long long x, int t)->long long { return (x + t - 1) / t; };
// Build the T>=2 block from the end: maintain R = required start for built suffix.
long long R = 0;
vector<int> picked_rev; picked_rev.reserve(n);
while (true) {
long long best = (1LL<<62);
int which = -1; // 2,3,4
if (has2()) {
long long cand = b2[i2].first + cdiv(R, 2);
if (cand < best || (cand == best && which < 2)) best = cand, which = 2;
}
if (has3()) {
long long cand = b3[i3].first + cdiv(R, 3);
if (cand < best || (cand == best && which < 3)) best = cand, which = 3;
}
if (has4()) {
long long cand = b4[i4].first + cdiv(R, 4);
if (cand < best || (cand == best && which < 4)) best = cand, which = 4;
}
if (which == -1) break; // no T>=2 left
if (best > (long long)A) break; // cannot extend the T>=2 block
if (which == 2) { picked_rev.push_back(b2[i2].second); ++i2; }
else if (which == 3) { picked_rev.push_back(b3[i3].second); ++i3; }
else { picked_rev.push_back(b4[i4].second); ++i4; }
R = best;
}
// Now append as many T=1 as possible (cheapest first) within remaining allowance A - R.
long long rem = (long long)A - R;
vector<int> one_tail;
for (size_t i = 0; i < b1.size(); ++i) {
if (b1[i].first <= rem) {
rem -= b1[i].first;
one_tail.push_back(b1[i].second);
} else break;
}
// Final order: reverse of picked_rev (since we built "last to first"), then the T=1 tail.
reverse(picked_rev.begin(), picked_rev.end());
picked_rev.insert(picked_rev.end(), one_tail.begin(), one_tail.end());
return picked_rev;
}
