#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef EVAL
#define dbg(expr) cerr << "[" << __FUNCTION__ << ", " << __LINE__ << "] " << #expr << ": " << expr << endl
#else
#define dbg(expr)
#endif
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vi = vector<int>;
using vvi = vector<vi>;
using a3 = array<ll, 3>;
using v3 = vector<a3>;
#define sz(c) ((int)c.size())
vi max_coupons(int _a, vi p, vi t) {
int n = sz(p);
assert(n == sz(t));
ll a = _a;
v3 coup;
v3 larg;
vector<pair<ll, int>> ones;
for (int i = 0; i < n; i++) {
if (t[i] > 1)
coup.push_back({p[i], t[i], i});
else
ones.push_back({p[i], i});
}
sort(ones.begin(), ones.end());
vl pref = {0};
for (auto [v, i] : ones)
pref.push_back(pref.back() + v);
if (sz(coup) == 0) {
int lo = 0;
int hi = sz(pref);
while (lo + 1 < hi) {
int mi = lo + (hi - lo) / 2;
if (pref[mi] <= a)
lo = mi;
else
hi = mi;
}
vi ret;
for (int i = 0; i < lo; i++)
ret.push_back(ones[i].second);
return ret;
}
sort(coup.begin(), coup.end(), [](auto lhs, auto rhs) {
auto [x, y, lind] = lhs;
auto [z, w, rind] = rhs;
return x * y * (w - 1) < z * w * (y - 1);
});
vi ret;
{
v3 coup2;
for (int i = 0; i < sz(coup); i++) {
ll na = max(min((a - coup[i][0]) * coup[i][1], (ll)1e15), (ll)-1);
if (na >= a) {
a = na;
ret.push_back(coup[i][2]);
} else
coup2.push_back(coup[i]);
}
coup = coup2;
}
for (auto [x, y, i] : coup) {
dbg(x); dbg(y); dbg(i);
}
vvl dp(sz(coup) + 1, vl(__bit_width(a) + 1, -1));
dp[0][0] = a;
for (int i = 1; i < sz(dp); i++) {
dp[i][0] = a;
for (int j = 1; j < sz(dp[0]); j++) {
dp[i][j] = max(dp[i - 1][j], max(min((dp[i - 1][j - 1] - coup[i - 1][0]) * coup[i - 1][1], (ll)1e15), (ll)-1));
}
}
vector<pair<int, int>> states;
for (int i = 0; i < sz(dp.back()); i++) {
ll mon = dp.back().at(i);
int len = i;
if (mon < 0)
continue;
dbg(len);
dbg(mon);
int lo = 0;
int hi = sz(pref);
while (lo + 1 < hi) {
int mi = lo + (hi - lo) / 2;
if (pref[mi] <= mon)
lo = mi;
else
hi = mi;
}
dbg(lo);
len += lo;
states.push_back({len, i});
}
int i = sz(dp) - 1;
auto [len, j] = *max_element(states.begin(), states.end());
len -= j;
dbg(i);
dbg(j);
vi dpi;
for (; i > 0 && j > 0; i--) {
dbg(dp[i][j]);
dbg(dp[i - 1][j]);
dbg(dp[i - 1][j - 1]);
int nj = j - (max(min((dp[i - 1][j - 1] - coup[i - 1][0]) * coup[i - 1][1], (ll)1e15), (ll)-1) == dp[i][j]);
dbg(i);
dbg(j);
if (nj != j)
dpi.push_back(coup[i - 1][2]);
j = nj;
}
reverse(dpi.begin(), dpi.end());
ret.insert(ret.end(), dpi.begin(), dpi.end());
for (int i = 0; i < len; i++)
ret.push_back(ones[i].second);
return ret;
}
