#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 1000000007;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
vector<pair<ll,ll>> srt;
vector<pair<ll,ll>> t1;
ll n = P.size();
for(ll i=0; i<n; i++) {
if(T[i] == 1) {
t1.push_back(make_pair(P[i], i));
} else {
ll x = 6 * T[i] / (T[i] - 1);
x *= P[i];
srt.push_back(make_pair(x, i));
}
}
sort(srt.begin(), srt.end()); sort(t1.begin(), t1.end());
vector<pair<ll,ll>> srt2;
vector<int> R; vector<bool> used(n,0);
ll B = A;
for(ll i=0; i<srt.size(); i++) {
if((B - P[srt[i].S]) * T[srt[i].S] >= B) {
R.push_back(srt[i].S);
used[srt[i].S] = 1;
B = (B - P[srt[i].S]) * T[srt[i].S];
if(B >= 1e18) {
for(ll i=0; i<n; i++) if(!used[i]) R.push_back(i);
return R;
}
} else srt2.push_back(srt[i]);
}
ll m = srt2.size();
vector<vector<pair<ll,ll>>> dp(m+1, vector<pair<ll,ll>>(67, make_pair(-1,-1)));
dp[0][0].F = B;
for(ll i=0; i<m; i++) for(ll j=0; j<67; j++) {
dp[i+1][j] = dp[i][j];
if(j > 0 && (dp[i][j-1].F - P[srt2[i].S]) * T[srt2[i].S] > dp[i+1][j].F) dp[i+1][j] = make_pair((dp[i][j-1].F - P[srt2[i].S]) * T[srt2[i].S], i);
}
vector<ll> smt1 = {0};
for(ll i=0; i<t1.size(); i++) smt1.push_back(smt1.back() + t1[i].F);
pair<ll,pair<ll,ll>> opt = make_pair(0, make_pair(0,0));
for(ll i=0; i<67; i++) {
if(dp.back()[i].F < 0) continue;
ll get = i - 1 + (upper_bound(smt1.begin(), smt1.end(), dp.back()[i].F) - smt1.begin());
if(get > opt.F) opt = make_pair(get, make_pair(i, get - i));
}
ll cur1 = m, cur2 = opt.S.F;
vector<int> Rv;
while(cur2 != 0) {
cur1 = dp[cur1][cur2].S;
cur2--;
Rv.push_back(srt2[cur1].S);
}
for(ll i=0; i<Rv.size(); i++) R.push_back(Rv[i]);
for(ll i=0; i<opt.S.S; i++) R.push_back(t1[i].S);
return R;
}
