#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
bool comp(pair<int, int> a, pair<int, int> b) {
return a.first * a.second * b.second + b.first * b.second < b.first * a.second * b.second + a.first * a.second;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
vector<pair<int, int>> vals;
for (int i = 0; i < P.size(); i++) {
vals.push_back({ P[i], T[i] });
}
sort(vals.begin(), vals.end(), comp);
vector<pair<int, int>> aa(P.size() + 1, { -1, -1 });
vector<vector<int>> p(P.size(), vector<int>(P.size(), -1));
aa[0] = { A, -1 };
for (int i = 0; i < P.size(); i++) {
for (int j = P.size() - 1; j >= 0; j--) {
if (aa[j].first < vals[i].first) continue;
if (aa[j + 1].first < (aa[j].first - vals[i].first) * vals[i].second) {
aa[j + 1] = { (aa[j].first - vals[i].first) * vals[i].second, i };
p[j][i] = aa[j].second;
}
}
}
int maxC = 0;
for (maxC = P.size(); maxC >= 0; maxC--) {
if (aa[maxC].first >= 0) break;
}
vector<int> res;
int crnt = aa[maxC].second;
while (crnt != -1) {
maxC--;
res.push_back(crnt);
crnt = p[maxC][crnt];
}
reverse(res.begin(), res.end());
return res;
}
