#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vll = vector<ll>;
using ui = unsigned int;
using vpii = vector<pii>;
using vvi = vector<vi>;
#define pb push_back
#define all(_) _.begin(), _.end()
constexpr int MXN = 200003;
constexpr ll INF = 200000000000000;
constexpr int MOD = 1;
constexpr int LOG = bit_width(ui(MXN));
int n;
struct coup{
int t, p, id;
coup(int a, int b, int c){
t = a;
p = b;
id = c;
}
};
bool comp(coup X, coup Y){
__int128 A = X.p*X.t*Y.p + Y.t*Y.p;
__int128 B = Y.p*Y.t*X.p + X.t*X.p;
return A < B;
}
ll dp[MXN][70]; // solo consideraremos los que quitan dinero, comprando aprox 60 te quedas pobre.
void retrieve(int i, vi& v, const vector<coup>& M){
vi rev;
while(n && i){
if(dp[n][i] != dp[n-1][i]) {
rev.pb(M[n-1].id);
i--;
}
n--;
}
reverse(all(rev));
v.insert(v.end(), all(rev));
}
vi max_coupons(int A, vi P, vi T){
vi answ;
n = T.size();
vpii T1;
vector<coup> M;
for(int i=0; i<n; i++){
if(T[i] == 1) T1.pb({P[i], i});
else M.pb(coup(T[i], P[i], i));
}
sort(all(T1));
sort(all(M), comp);
n = M.size();
__int128 X = A;
int k=0;
while(k<n){
auto [t,p, id] = M[k];
__int128 newX = (X - p)*t;
if(newX >= INF){ // si ya tenemos plata para comprar todo.
answ.clear();
for(auto &[t,p,id] : M) answ.pb(id);
for(auto &[p, id] : T1) answ.pb(id);
return answ;
}
if(newX >= X){
X = newX;
k++;
answ.pb(id);
}
else break;
}
for(int i=0; i<n; i++) dp[i][0] = X;
for(int i=k+1; i<n; i++){
auto [t,p,id] = M[i-1];
int tope = min(70, i-k);
for(int j=1; j<tope; j++){
dp[i][j] = max(dp[i][j], (dp[i-1][j-1] - p)*t);
}
}
ll MaxNormal = 0;
ll MaxT1 = 0;
for(int i=0; i<70; i++){
pii din = {dp[n][i], -1};
int extra = upper_bound(all(T1), din) - T1.begin();
if(i+extra > MaxNormal + MaxT1){
MaxNormal = i;
MaxT1 = extra;
}
}
retrieve(MaxNormal, answ, M);
for(int i=0; i<MaxT1; i++) answ.pb(T1[i].second);
return answ;
}
