#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
constexpr int N = 71;
constexpr int64_t inf = 1e14;
pair<int64_t, vector<int>> dp[N][N];
vector<int> max_coupons(int A, vector<int> p, vector<int> t) {
int n = p.size();
auto get = [&](vector<int> b) {
int x = A;
for (auto i : b) {
if (x >= p[i]) {
x = (x - p[i]) * t[i];
}
}
return x;
};
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = {-inf, vector<int>{}};
}
}
if (A >= p[0]) {
dp[0][1] = {A - p[0], vector<int>{0}};
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= i + 1; j++) {
if (dp[i - 1][j - 1].first < 0) continue;
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
vector<int> b = dp[i - 1][j - 1].second;
int m = b.size();
b.push_back(i);
int mx = get(b);
vector<int> res;
if (mx > 0) {
res = b;
}
for (int k = m - 1; k >= 0; k--) {
swap(b[k], b[k + 1]);
int ret = get(b);
if (ret > mx) {
mx = ret;
res = b;
}
}
dp[i][j] = {mx, res};
}
}
int mx = 0;
vector<int> res;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= n; j++) {
auto [k, v] = dp[i][j];
if (k > mx) {
mx = k;
res = v;
}
}
}
return res;
}
