#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
struct Coupon {
int idx; // original index
long long p; // price
int t; // type (multiplier)
bool inf; // true for T == 1 (key = +infinity)
__int128 num; // P * T (valid only if !inf)
__int128 den; // T-1 (valid only if !inf)
};
static bool cmpCoupon(const Coupon& a, const Coupon& b) {
if (a.inf != b.inf) // finite keys come first
return !a.inf && b.inf;
if (a.inf) // both infinite – any order, keep by idx
return a.idx < b.idx;
// compare a.num / a.den < b.num / b.den
return a.num * b.den < b.num * a.den;
}
std::vector<int> max_coupons(int A, std::vector<int> P,
std::vector<int> T) {
int N = (int)P.size();
vector<Coupon> coupons(N);
for (int i = 0; i < N; ++i) {
coupons[i].idx = i;
coupons[i].p = P[i];
coupons[i].t = T[i];
coupons[i].inf = (T[i] == 1);
if (!coupons[i].inf) {
coupons[i].num = (__int128)P[i] * (__int128)T[i];
coupons[i].den = (__int128)(T[i] - 1);
}
}
// sort by increasing key = P*T/(T-1); T==1 -> +inf
sort(coupons.begin(), coupons.end(), cmpCoupon);
// reverse order: we will add coupons in front of the already built suffix
vector<int> orderDesc(N); // original indices in descending key order
for (int i = 0; i < N; ++i) {
orderDesc[i] = coupons[N - 1 - i].idx; // biggest key first
}
const long long INF = (1LL << 60); // large enough ( > sum of all prices )
vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, INF));
vector<vector<char>> take(N + 1, vector<char>(N + 1, 0));
dp[0][0] = 0;
for (int i = 1; i <= N; ++i) {
int idx = orderDesc[i - 1];
long long Pi = P[idx];
int Ti = T[idx];
for (int k = 0; k <= i; ++k) {
// option 1: skip this coupon
long long best = dp[i - 1][k];
char used = 0;
// option 2: take it
if (k > 0 && dp[i - 1][k - 1] != INF) {
long long prev = dp[i - 1][k - 1];
long long cand = Pi + (prev + Ti - 1) / Ti; // ceil(prev / Ti)
if (cand < best) {
best = cand;
used = 1;
}
}
dp[i][k] = best;
take[i][k] = used;
}
}
int bestK = 0;
for (int k = N; k >= 0; --k) {
if (dp[N][k] <= A) {
bestK = k;
break;
}
}
// reconstruct the answer
vector<int> answer;
int i = N, k = bestK;
while (i > 0) {
if (take[i][k]) {
answer.push_back(orderDesc[i - 1]); // this coupon is used
--k;
}
--i;
}
// 'answer' is already in forward chronological order (lowest key first)
return answer;
}
