#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 3e15;
const int N = 2e5+4;
const int ANS = 70;
struct coupon{
int p, t, idx;
int apply(int tk){
tk -= p; tk *= t;
if (tk > INF) tk = INF;
if (tk < 0) tk = -1;
return tk;
}
};
bool comp(coupon &a, coupon &b){
if (a.t == 1 && b.t == 1) return a.p < b.p;
return a.p * a.t * (b.t - 1) < b.p * b.t * (a.t - 1);
}
int dp[N][ANS];
int us[N][ANS];
vector<signed> max_coupons(signed A, vector<signed> P, vector<signed> T) {
int n = P.size();
vector<coupon> cp, ones;
for (int i=0; i<n; i++){
if (T[i] == 1) ones.push_back({P[i], T[i], i});
else cp.push_back({P[i], T[i], i});
}
sort(cp.begin(), cp.end(), comp);
vector<int> pr = {0};
for (auto [p, t, idx]: ones) pr.push_back(pr.back() + p);
for (int i=0; i<N; i++) for (int j=0; j<ANS; j++) dp[i][j] = -1;
dp[0][0] = A;
for (int i=1; i<=cp.size(); i++){
coupon cn = cp[i-1];
for (int j=0; j<ANS; j++) dp[i][j] = dp[i-1][j];
for (int j=1; j<ANS; j++) {
if (dp[i][j] > cn.apply(dp[i-1][j-1])) continue;
dp[i][j] = cn.apply(dp[i-1][j-1]);
us[i][j] = 1;
}
}
int mx = 0, mt = 0;
for (int i=0; i<ANS; i++){
int l = 0, r = pr.size() - 1;
if (dp[cp.size()][i] < 0) continue;
while (l<r){
int m = (l+r+1)/2;
if (pr[m] <= dp[cp.size()][i]) l = m; else r = m-1;
}
if (i + l > mx) mx = i+l, mt = i;
}
vector<signed> ans;
int i = cp.size(); int m = mt; int left = dp[i][mt];
while (i){
if (!us[i][m]) {i--; continue;}
i--; m--;
ans.push_back(cp[i].idx);
}
reverse(ans.begin(), ans.end());
for (int i=0; i<ones.size(); i++) {
if (left < ones[i].p) break;
left = ones[i].apply(left);
ans.push_back(ones[i].idx);
}
return ans;
}
