#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
const ll INF = 1e17;
std::vector<int> max_coupons(int AA, std::vector<int> P, std::vector<int> T) {
ll A = AA;
v<v<int>> order;
v<v<int>> ones;
int N = P.size();
rep(i, 0, N) {
if (T[i] != 1) order.push_back({P[i], T[i], i});
else ones.push_back({P[i], i});
}
sort(order.begin(), order.end(), [&](v<int> a, v<int> b) {
ll v1 = -a[0]*a[1]*b[1] - b[0]*b[1];
ll v2 = -b[0]*b[1]*a[1] - a[0]*a[1];
return v1 > v2;
});
sort(ones.begin(), ones.end());
v<v<ll>> dp(N+1, v<ll>(71, -1));
v<v<int>> par(N+1, v<int>(71, -1));
int beg=0;
for (auto x : order) {
ll p = x[0], t = x[1];
if ((A-p)*t >= A) {
A = (A-p)*t;
A = min(A, INF);
beg++;
}
}
rep(i, 0, N+1) {
dp[i][0] = A;
}
int M = order.size();
rep(i, beg+1, M+1) {
ll p = order[i-1][0];
ll t = order[i-1][1];
rep(j, 0, 71) {
if (dp[i-1][j] >= 0) {
dp[i][j] = dp[i-1][j];
par[i][j] = 0;
}
}
rep(j, 0, 70) {
if (dp[i-1][j] >= p) {
ll val = (dp[i-1][j]-p)*t;
val = min(val, INF);
if (val > dp[i][j+1]) {
dp[i][j+1] = val;
par[i][j+1] = 1;
}
}
}
}
int K = ones.size();
v<ll> pref(K+1, 0);
rep(i, 1, K+1) {
pref[i] = pref[i-1] + ones[i-1][0];
}
int mx = -1, id=-1, one=-1;
rep(j, 0, 70) {
if (dp[M][j] >= 0) {
int val = j;
int l = 1, r = K;
int anss=0;
while (l <= r) {
int m = (l+r)/2;
if (pref[m] <= dp[M][j]) {
l = m+1;
anss = m;
}
else r=m-1;
}
val += anss;
if (val > mx) {
mx = val;
id = j;
one = anss;
}
}
}
v<int> ans;
rep(i, 0, one) {
ans.push_back(ones[i][1]);
}
for (int i = M; i >= beg; i--) {
if (par[i][id] == 1) {
id--;
ans.push_back(order[i-1][2]);
}
}
for (int i = beg-1; i >= 0; i--) {
ans.push_back(order[i][2]);
}
reverse(ans.begin(), ans.end());
return ans;
}
