#include "bits/stdc++.h"
using namespace std;
#include "festival.h"
typedef long long ll;
const ll lim = 1e18;
vector<int> max_coupons(int Ai, vector<int> Pi, vector<int> Ti){
ll A = (ll) Ai;
vector<ll> P, T;
for (auto &e: Pi) P.push_back((ll) e);
for (auto &e: Ti) T.push_back((ll) e);
ll N = P.size();
vector<ll> R;
vector<ll> type1, temp;
for (int i = 0; i < N; i++) {
if (T[i] == 1) type1.push_back(i);
else temp.push_back(i);
}
sort(type1.begin(), type1.end(), [&](ll& a, ll& b){return P[a] < P[b];});
ll t1s = type1.size();
vector<ll> pre(t1s + 1, -1);
pre[0] = 0;
for (int i = 0; i < t1s; i++){
pre[i+1] = pre[i] + P[type1[i]];
pre[i+1] = min(pre[i+1], lim);
}
sort(temp.begin(), temp.end(), [&](ll& a, ll& b){return T[b]*P[b]*(T[a] - 1) > T[a]*P[a]*(T[b] - 1);});
ll ts = temp.size();
ll oldM = A, lowI = -1;
for (int i = 0; i < ts; i++){
ll newM = (oldM - P[temp[i]])*T[temp[i]];
newM = min(newM, lim);
if (newM < oldM){ lowI = i; break; }
oldM = newM;
}
if (lowI == -1) lowI = ts;
for (int i = 0; i < lowI; i++) R.push_back(temp[i]);
if (lowI < ts){
vector<ll> t;
map<ll, ll> frq;
for (int i = lowI; i < ts; i++){
frq[T[temp[i]]]++;
if (frq[T[temp[i]]] <= 32) t.push_back(temp[i]);
}
ts = t.size();
vector<vector<ll>> dp(ts+1, vector<ll>(ts+1, -1)), log(ts+1, vector<ll>(ts+1, -1));
dp[0][0] = oldM;
for (int i = 1; i <= ts; i++){
for (int j = 0; j < i; j++){
dp[i][j] = dp[i - 1][j];
if (dp[i][j] < 0) break;
dp[i][j] = min(dp[i][j], lim);
}
for (int j = 1; j <= i; j++){
ll val = (dp[i-1][j-1] - P[t[i-1]]) * T[t[i-1]];
val = min(val, lim);
if (val >= dp[i][j]) dp[i][j] = val, log[i][j] = j;
if (dp[i][j] < 0) break;
dp[i][j] = min(dp[i][j], lim);
}
}
ll maxCount = 0, t1Count = 0, tCount = 0;
for (int i = 0; i <= ts; i++){
oldM = min(dp[ts][i], lim);
ll pos = upper_bound(pre.begin(), pre.end(), oldM) - pre.begin() - 1;
pos = min(pos, t1s), pos = max(pos, 0ll);
if (pos + i >= maxCount && oldM - pre[pos] >= 0) maxCount = pos + i, t1Count = pos, tCount = i;
}
vector<ll> R2;
ll b = 0, i = ts, j = tCount;
for (; i > 0; i--){
if (b >= tCount) break;
if (log[i][j] >= 0) R2.push_back(t[i-1]), b++, j = log[i][j] - 1;
}
reverse(R2.begin(), R2.end());
for (auto &e: R2) R.push_back(e);
for (int i = 0; i < t1Count; i++) R.push_back(type1[i]);
} else {
for (int i = 1; i <= t1s; i++)
if (pre[i] <= oldM) R.push_back(type1[i-1]);
}
vector<int> intR;
for (auto &e: R) intR.push_back((int) e);
return intR;
}
