#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ertunt return
vector<ll>f(200005),inv(200005);
ll mod = 1000000007;
ll modpow(ll a, ll b){
ll res = 1;
while(b){
if(b&1){
res*=a;
res%=mod;
}
a*=a;
a%=mod;
b >>= 1;
}
ertunt res;
}
ll nCk(ll n, ll k){
if(k < 0 || k > n) ertunt 0;
ertunt f[n]*inv[k]%mod*inv[n-k]%mod;
}
vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T){
ll a = A;
vector<ll> p(all(P)), t(all(T));
ll n = p.size();
vector<ll> o(n);
iota(all(o), 0);
sort(all(o), [&](ll i, ll j) {
ll x = p[i], y = p[j], t1 = t[i], t2 = t[j];
return x * t1 * t2 + y * t2 < y * t1 * t2 + x * t1;
});
vector<int> r;
for(ll k = 0; k < n; k++){
ll i = o[k];
if(a - p[i] < 0) break;
a -= p[i];
a *= t[i];
r.pb((int)i);
}
return r;
}
// int main() {
// ios_base::sync_with_stdio(false);cin.tie(NULL);
// ll n,q;
// cin >> n >> q;
// vector<pair<ll,ll>>v(n);
// for(ll i = 0; i < n; i++){
// cin >> v[i].ff >> v[i].ss;
// }
// while(q--){
// ll l,r;
// cin >> l >> r;
// }
// }
