#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e15;
vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
int n = p.size();
vector<array<int, 3>> pt1;
vector<array<int, 2>> pt2;
for (int i = 0; i < n; i++) {
if (t[i] != 1) {
pt1.push_back({p[i], t[i], i});
} else {
pt2.push_back({p[i], i});
}
}
sort(pt1.begin(), pt1.end(), [&](array<int, 3> x, array<int, 3> y) {
if (x[1] == 1 && y[1] == 1) {
return (x[0] < y[0]);
}
int p1 = x[0], p2 = y[0], t1 = x[1], t2 = y[1];
return (static_cast<long long>(p1) * static_cast<long long>(t1) * static_cast<long long>(t2 - 1) < static_cast<long long>(p2) * static_cast<long long>(t2) * static_cast<long long>(t1 - 1));
});
sort(pt2.begin(), pt2.end());
int m = pt1.size(), k = pt2.size();
vector<vector<long long>> dp(n + 1, vector<long long>(40, -inf)), take(n + 1, vector<long long>(40, -1));
int las = 0;
long long awa = a;
for (auto [pp, tt, _] : pt1) {
if (static_cast<long long>(tt) * static_cast<long long>(awa - pp) >= awa) {
awa = static_cast<long long>(tt) * static_cast<long long>(awa - pp);
awa = min(awa, inf);
las++;
} else {
break;
}
}
for (int i = 0; i <= n; i++) {
dp[i][0] = awa;
}
for (int i = las + 1; i <= m; i++) {
auto [pp, tt, _] = pt1[i - 1];
for (int j = 0; j < 40; j++) {
if (dp[i - 1][j] >= 0) {
dp[i][j] = dp[i - 1][j];
take[i][j] = 0;
}
}
for (int j = 0; j < 39; j++) {
if (dp[i - 1][j] >= pp) {
long long val = static_cast<long long>(dp[i - 1][j] - pp) * static_cast<long long>(tt);
val = min(val, inf);
if (val > dp[i][j + 1]) {
dp[i][j + 1] = val;
take[i][j + 1] = 1;
}
}
}
}
vector<long long> pref(k + 1);
for (int i = 1; i <= k; i++) {
pref[i] = pref[i - 1] + pt2[i - 1][0];
}
int mx = -1, id = -1, idx = -1;
for (int i = 0; i < 40; i++) {
if (dp[m][i] >= 0) {
int val = i;
int low = 0, high = k, idxx = -1;
while (low <= high) {
int mid = (low + high) >> 1;
if (pref[mid] <= dp[m][i]) {
idxx = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
val += low;
if (val > mx) {
mx = val;
id = i;
idx = idxx;
}
}
}
vector<int> ans;
for (int i = 0; i < idx; i++) {
ans.push_back(pt2[i][1]);
}
for (int i = m; i > las; i--) {
if (take[i][id] == 1) {
id--;
ans.push_back(pt1[i - 1][2]);
}
}
for (int i = las - 1; i >= 0; i--) {
ans.push_back(pt1[i][2]);
}
reverse(ans.begin(), ans.end());
return ans;
}
