#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, k;
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.t + Y.t*Y.p;
__int128 B = Y.p*Y.t*X.t + 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>k && i){
auto [t, p, id] = M[n-1];
if(dp[n-1][i-1] >= p && dp[n][i] == (dp[n-1][i-1] - p)*t) {
rev.pb(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(M), comp);
if(T1.size()){
sort(all(T1));
n = T1.size();
vll prefT1(n);
prefT1[0] = T1[0].first;
for(int i=1; i<n; i++) prefT1[i] = prefT1[i-1] + T1[i].first;
}
n = M.size();
__int128 X = A;
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++) {
for(int j=0; j<70; j++) dp[i][j] = -1;
}
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(69, i-k);
for(int j=1; j<=tope; j++){
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] < p ? -1 : (dp[i-1][j-1] - p)*t);
}
}
ll MaxNormal = 0;
ll MaxT1 = 0;
for(int i=0; i<70; i++){
ll din = dp[n][i];
int extra = upper_bound(all(prefT1), din) - prefT1.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;
}
