#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; // } // }