#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
struct Coupon {
int idx; // original index
long long p; // price
int t; // type (multiplier)
};
int N = (int)P.size();
vector<Coupon> c(N);
for (int i = 0; i < N; ++i) c[i] = {i, (long long)P[i], T[i]};
/* Order that minimises the needed initial tokens.
For T>1 the key is V = P * T / (T-1) .
Coupons with T = 1 are placed at the end (they never increase tokens). */
auto cmp = [](const Coupon& a, const Coupon& b) {
if (a.t == 1 && b.t == 1) return a.idx < b.idx; // any stable order
if (a.t == 1) return false; // a after b
if (b.t == 1) return true; // a before b
// compare a.p * a.t * (b.t-1) < b.p * b.t * (a.t-1)
long long left = a.p * a.t * (b.t - 1LL);
long long right = b.p * b.t * (a.t - 1LL);
if (left != right) return left < right;
// deterministic tie‑break
if (a.t != b.t) return a.t < b.t;
return a.p < b.p;
};
sort(c.begin(), c.end(), cmp);
const long long INF = (1LL << 60);
// dp[i][k] = minimal tokens needed before processing items i..N-1
// to buy exactly k coupons among them (respecting the order)
vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, INF));
dp[N][0] = 0;
for (int i = N - 1; i >= 0; --i) {
dp[i][0] = 0;
for (int k = 1; k <= N - i; ++k) {
long long best = dp[i + 1][k]; // skip current coupon
long long prev = dp[i + 1][k - 1]; // take it
if (prev != INF) {
long long cand = c[i].p + ( (prev + c[i].t - 1) / c[i].t );
if (cand < best) best = cand;
}
dp[i][k] = best;
}
}
long long A_ll = A;
int bestK = 0;
for (int k = N; k >= 0; --k) {
if (dp[0][k] <= A_ll) { bestK = k; break; }
}
// reconstruct one optimal sequence (forward order = the order in 'c')
vector<int> answer;
answer.reserve(bestK);
int i = 0, k = bestK;
while (i < N && k > 0) {
if (dp[i][k] == dp[i + 1][k]) {
++i; // skip this coupon
} else {
answer.push_back(c[i].idx); // take it
--k;
++i;
}
}
return answer;
}
