#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();
// Split into T=1 and multipliers T>=2
vector<pair<int,int>> t1; // (price, idx)
struct MItem {
long long key; // w(T) * P key
int p, t, idx;
};
vector<MItem> mult;
int maxP = 0;
ll sumT1 = 0;
auto weight = [](int t) -> int {
// Sorting by s = P*T/(T-1). Multiply by 6 to avoid fractions:
// T=2 -> 12, T=3 -> 9, T=4 -> 8
if (t == 2) return 12;
if (t == 3) return 9;
// t == 4
return 8;
};
for (int i = 0; i < N; ++i) {
maxP = max(maxP, P[i]);
if (T[i] == 1) {
t1.emplace_back(P[i], i);
sumT1 += (ll)P[i];
} else {
int w = weight(T[i]);
mult.push_back(MItem{ (ll)w * (ll)P[i], P[i], T[i], i });
}
}
// Sort multipliers by key, then by price, then by index for determinism
sort(mult.begin(), mult.end(), [](const MItem& a, const MItem& b) {
if (a.key != b.key) return a.key < b.key;
if (a.p != b.p) return a.p < b.p;
if (a.t != b.t) return a.t < b.t;
return a.idx < b.idx;
});
// Sort T=1 by ascending price, tie-break by index
sort(t1.begin(), t1.end(), [](const pair<int,int>& a, const pair<int,int>& b){
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
});
// Prefix sums for T=1
vector<ll> pref1(1, 0);
pref1.reserve(t1.size() + 1);
for (auto &e : t1) pref1.push_back(pref1.back() + (ll)e.first);
// Cap to avoid overflow while preserving correctness:
// Must be >= max price to not break feasibility checks, and >= sum of T1
// so we don't undercount purchasable T1.
ll cap = sumT1 + (ll)maxP + 1;
// Simulate all feasible prefixes of multipliers
vector<ll> after; // tokens after buying first k multipliers
after.reserve(mult.size() + 1);
ll tokens = (ll)A;
after.push_back(tokens);
int F = 0; // number of feasible multipliers in order
for (int i = 0; i < (int)mult.size(); ++i) {
tokens = min(tokens, cap);
if (tokens < mult[i].p) break; // can't afford next multiplier
ll ntok = (tokens - (ll)mult[i].p) * (ll)mult[i].t;
if (ntok > cap) ntok = cap;
tokens = ntok;
after.push_back(tokens);
++F;
}
// For each feasible prefix k, buy as many T=1 as possible and track the best
int best_k = 0, best_r = 0;
ll best_total = -1;
for (int k = 0; k <= F; ++k) {
ll cur = after[k];
// r = largest with pref1[r] <= cur
int r = (int)(upper_bound(pref1.begin(), pref1.end(), cur) - pref1.begin()) - 1;
ll total = (ll)k + (ll)r;
if (total > best_total) {
best_total = total;
best_k = k;
best_r = r;
} else if (total == best_total) {
// Optional tie-breaker: prefer more multipliers
if (k > best_k) {
best_k = k;
best_r = r;
}
}
}
// Build the actual purchase order: first the chosen multipliers, then chosen T=1
vector<int> order;
order.reserve(best_k + best_r);
for (int i = 0; i < best_k; ++i) order.push_back(mult[i].idx);
for (int i = 0; i < best_r; ++i) order.push_back(t1[i].second);
return order;
}
