#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;
const ll INF = 200005000000009;
struct ban
{
int i;
ll p, t;
};
ll F(ll A, const ban& u)
{
return (A - u.p) * u.t;
}
bool operator<(const ban& a, const ban& b)
{
return F(F(0, a), b) < F(F(0, b), a);
}
std::vector<int> max_coupons(int aa, std::vector<int> P, std::vector<int> T)
{
int n;
n = sz(P);
vector<pair<ll, ban> > v;
for (int i = 0; i < n; ++i)
{
ban u;
u.p = P[i];
u.t = T[i];
u.i = i;
if (u.t == 1)
v.push_back(m_p(INF, u));
else
{
ll x = u.p * u.t;
if (x % (u.t - 1) == 0)
x /= (u.t - 1);
else
{
x /= (u.t - 1);
++x;
}
v.push_back(m_p(x, u));
}
}
sort(all(v));
reverse(all(v));
priority_queue<ban> q;
ll A = aa;
vector<int> ans;
while (1)
{
while (!v.empty() && A >= v.back().fi)
{
q.push(v.back().se);
v.pop_back();
}
if (q.empty())
break;
ban u = q.top();
q.pop();
A = min(INF, (A - u.p) * u.t);
ans.push_back(u.i);
}
for (int i = 0; i < sz(v); ++i)
v[i].fi = 0;
sort(all(v));
reverse(all(v));
vector<ban> u;
while (!v.empty() && v.back().se.t == 1)
{
u.push_back(v.back().se);
v.pop_back();
}
reverse(all(u));
vector<ll> p(sz(u) + 1, 0);
for (int i = 0; i < sz(u); ++i)
p[i + 1] = p[i] + u[i].p;
const int M = 200;
vector<vector<ll> > dp(sz(v) + 1, vector<ll>(M, -1));
dp[0][0] = A;
for (int i = 0; i < sz(v); ++i)
{
ban u = v[i].se;
for (int q = 0; q < M - 1; ++q)
{
dp[i + 1][q] = max(dp[i + 1][q], dp[i][q]);
if (dp[i][q] >= u.p)
dp[i + 1][q + 1] = max(dp[i + 1][q + 1], (dp[i][q] - u.p) * u.t);
}
}
int maxu = 0;
for (int q = 0; q < M; ++q)
{
if (dp[sz(v)][q] >= 0)
{
int l = 0, r = sz(u);
int qq = -1;
while (l <= r)
{
int m = (l + r) / 2;
if (dp[sz(v)][q] >= p[m])
{
qq = m;
l = m + 1;
}
else
r = m - 1;
}
assert(qq != -1);
maxu = max(maxu, q + qq);
}
}
vector<int> yans;
for (int q = 0; q < M; ++q)
{
if (dp[sz(v)][q] >= 0)
{
int l = 0, r = sz(u);
int qq = -1;
while (l <= r)
{
int m = (l + r) / 2;
if (dp[sz(v)][q] >= p[m])
{
qq = m;
l = m + 1;
}
else
r = m - 1;
}
if (maxu == q + qq)
{
for (int i = sz(v) - 1; i >= 0; --i)
{
if (dp[i + 1][q] == dp[i][q])
continue;
yans.push_back(v[i].se.i);
--q;
}
reverse(all(yans));
for (int i = 0; i < qq; ++i)
yans.push_back(u[i].i);
break;
}
}
}
for (int i = 0; i < sz(yans); ++i)
ans.push_back(yans[i]);
return ans;
}
/*
4 13
4 1
500 3
8 3
14 4
2 1000
999 4
3 1
*/
