#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);
}
int l = 0, r = sz(v) - 1;
int u = -1;
while (l <= r)
{
int m = (l + r) / 2;
ll x = A;
for (int i = m; i >= 0; --i)
{
ban u = v[i].se;
x = (x - u.p) * u.t;
if (x < 0)
break;
}
if (x >= 0)
{
u = m;
l = m + 1;
}
else
r = m - 1;
}
for (int i = u; i >= 0; --i)
ans.push_back(v[i].se.i);
return ans;
}
/*
4 13
4 1
500 3
8 3
14 4
*/
