#include <bits/stdc++.h>
//#include "festival.h"
using namespace std;
std::vector <int> max_coupons(int A, std::vector <int> P, std::vector <int> T) {
auto compare = [&](int i, int j) {
std::pair <int, int> a = std::make_pair(P[i], T[i]);
std::pair <int, int> b = std::make_pair(P[j], T[j]);
return (1LL * a.first * a.second * b.second + 1LL * b.first * b.second < 1LL * b.first * a.second * b.second + 1LL * a.first * a.second);
};
auto compareOne = [&](int i, int j) {
return P[i] < P[j];
};
std::vector <int> ones, other;
for (int i = 0; i < (int) T.size(); i++) {
if (T[i] == 1) {
ones.push_back(i);
}
else {
other.push_back(i);
}
}
std::sort(ones.begin(), ones.end(), compareOne);
std::sort(other.begin(), other.end(), compare);
std::cout << std::endl;
int n = (int) ones.size();
int numbT = std::min(30, (int) other.size());
std::vector <long double> mul(numbT + 1);
mul[0] = 1LL;
for (int i = 1; i <= numbT; i++) {
mul[i] = (long double) mul[i - 1] * T[other[i - 1]];
}
const double inf = -1.0000;
std::vector <std::vector <std::pair <int, int>>> trace(n + 1);
std::vector <std::vector <long long>> f(n + 1);
for (int i = 0; i <= n; i++) {
f[i].resize(numbT + 1, inf);
trace[i].resize(numbT + 1, std::make_pair(-1, -1));
}
f[0][0] = (long long) A;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= numbT; j++) {
if (f[i][j] < 0.0) {
continue;
}
if (i < n && f[i][j] >= P[ones[i]]) {
if (f[i + 1][j] < f[i][j] - P[ones[i]]) {
f[i + 1][j] = f[i][j] - P[ones[i]];
trace[i + 1][j] = std::make_pair(i, j);
}
}
if (j < numbT && f[i][j] >= P[other[j]]) {
if (f[i][j + 1] < (long long) (f[i][j] - P[other[j]]) * T[other[j]]) {
f[i][j + 1] = (long long) (f[i][j] - P[other[j]]) * T[other[j]];
trace[i][j + 1] = std::make_pair(i, j);
}
}
}
}
std::vector <int> ret;
int maxNumb = -1;
int posi = -1, posj = -1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= numbT; j++) {
if (maxNumb < i + j && f[i][j] != inf) {
maxNumb = i + j;
posi = i;
posj = j;
}
}
}
while (posi > 0 || posj > 0) {
std::pair <int, int> prev = trace[posi][posj];
if (prev.second == posj) {
ret.push_back(ones[prev.first]);
posi = prev.first;
}
else {
ret.push_back(other[prev.second]);
posi = prev.first;
posj = prev.second;
}
}
std::reverse(ret.begin(), ret.end());
return ret;
}
