#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
const ll INF = 1e17;
const int MAXN = 2e5 + 7;
const int K = 200;
ll dp[MAXN][K];
pii last[MAXN][K];
pll f(pll x) {
if (x.nd == 2ll) {
return {x.st, 1};
}
if (x.nd == 3ll) {
return {x.st * 3ll, 4ll};
}
return {x.st * 2ll, 3ll};
}
bool por(pair<pll, int> a, pair<pll, int> b) {
pll x = f(a.st);
pll y = f(b.st);
return ((x.st * y.nd) < (y.st * x.nd));
}
ll lic(ll x, pll p) {
return ((x - p.st) * p.nd);
}
std::vector<int> max_coupons(int A, std::vector<int> P1, std::vector<int> T1) {
int n = P1.size();
vector<pair<pll, int>> tab;
vector<pair<ll, int>> pom;
rep(i, n) {
if (T1[i] == 1) {
pom.pb({P1[i], i});
}
else {
tab.pb({{P1[i], T1[i]}, i});
}
}
sort(all(tab), por);
sort(all(pom));
pair<pll, int> T[n];
int it = 0;
for (auto p: tab) {
T[it] = p;
it++;
}
for (auto p: pom) {
T[it] = {{p.st, 1ll}, p.nd};
it++;
}
ll val = A;
vector<int> ans;
bool dodan[n];
rep(i, n) {
dodan[i] = false;
}
it = 0;
rep(i, n) {
if (val >= INF) {
for (auto x: ans) {
dodan[x] = true;
}
rep(j, n) {
if (dodan[j]) continue;
ans.pb(j);
}
return ans;
}
if (lic(val, T[i].st) >= val) {
val = lic(val, T[i].st);
ans.pb(T[i].nd);
}
else break;
it = i + 1;
}
rep(i, n + 1) {
rep(j, K) {
dp[i][j] = -1;
}
}
dp[it][0] = val;
// cout << "val = " << val << '\n';
int n2 = tab.size();
// cout << "it = " << it << " n2 = " << n2 << '\n';
for (int i = it; i < n2; i++) {
dp[i + 1][0] = dp[i][0];
rep(j, K - 1) {
dp[i + 1][j + 1] = dp[i][j + 1];
last[i + 1][j + 1] = last[i][j + 1];
ll nowa = (dp[i][j] - T[i].st.st) * T[i].st.nd;
if (nowa > dp[i + 1][j + 1]) {
dp[i + 1][j + 1] = nowa;
last[i + 1][j + 1] = {i, T[i].nd};
}
}
}
int sz = pom.size();
ll pref[sz + 1];
pref[0] = 0ll;
rep(i, sz) {
pref[i + 1] = pref[i] + pom[i].st;
}
int maks = 0;
int kt = sz;
int il2 = 0;
int kt2 = 0;
rep(il, K) {
if (dp[n2][il] < 0) break;
while (kt > 0 && (pref[kt] > dp[n2][il])) {
kt--;
}
if ((kt + il) > maks) {
maks = kt + il;
il2 = il;
kt2 = kt;
}
}
int it1 = n2;
// cout << "kt2 = " << kt2 << " il2 = " << il2 << '\n';
while (il2 > 0) {
ans.pb(last[it1][il2].nd);
it1 = last[it1][il2].st;
il2--;
}
rep(i, kt2) {
ans.pb(pom[i].nd);
}
return ans;
}
