#include "bits/stdc++.h"
using namespace std;
#include "festival.h"
typedef long long ll;
const ll lim = 1e18;
#define chk
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
vector<int> R;
ll N = P.size();
vector<vector<ll>> t1, t;
vector<ll> pre1(N+1, lim*2);
for (ll i = 0; i < N; i++){
if (T[i] == 1) t1.push_back({P[i], i});
else t.push_back({P[i], i, T[i]});
}
ll t1s = t1.size(), ts = t.size();
sort(t1.begin(), t1.end());
sort(t.begin(), t.end(), [](vector<ll>& a, vector<ll>& b){
ll l = a[2]*((b[0]*b[2]) + a[0]), r = b[2]*((a[0]*a[2]) + b[0]);
return l > r;
});
vector<vector<ll>> dp(ts + 1, vector<ll>(ts + 1, -1)), log(ts + 1, vector<ll>(ts + 1, -1));
dp[0][0] = A;
for (int i = 1; i <= ts; i++){
for (int j = 0; j < i; j++){
dp[i][j] = dp[i - 1][j];
if (dp[i][j] < 0) break;
dp[i][j] = min(dp[i][j], lim);
}
for (int j = 1; j <= i; j++){
ll val = (dp[i - 1][j - 1] - t[i-1][0])*t[i-1][2];
if (val >= dp[i][j]){
dp[i][j] = val;
log[i][j] = j;
}
if (dp[i][j] < 0) break;
dp[i][j] = min(dp[i][j], lim);
}
}
pre1[0] = 0;
for (ll i = 0; i < t1s; i++)
pre1[i + 1] = pre1[i] + t1[i][0], pre1[i + 1] = min(pre1[i + 1], lim);
ll mc = 0ll, mt1 = 0ll, mt = 0ll, ct1 = 0ll;
for (ll i = 0; i <= ts; i++){
if (dp[ts][i] < 0) break;
ll pos = upper_bound(pre1.begin(), pre1.end(), dp[ts][i]) - pre1.begin();
if (pos == 0) ct1 = 0;
else ct1 = min(pos - 1, t1s);
if (ct1 + i > mc) mc = ct1 + i, mt1 = ct1, mt = i;
}
int cur = mt, c = ts, b = 0;
while (R.size() < mt){
if (log[c][cur] >= 0){
R.push_back(t[c-1][1]);
b++;
}
cur = mt - b, c--;
}
reverse(R.begin(), R.end());
for (ll i = 0; i < mt1; i++) R.push_back(t1[i][1]);
return R;
}
