Matei vrea sa cumpere cel putin T pungi de bomboane, fiecare punga costand 1 leu. El are la dispozitie k oferte, dintre care trebuie sa aleaga cel mult una (dar o poate folosi de oricate ori). Oferta i este de forma: 'pentru fiecare a_i pungi cumparate, urmatoarele b_i sunt gratuite', adica daca plateste x pungi, primeste in plus b_i * floor(x / a_i) pungi gratuite, deci primeste in total x + b_i * floor(x / a_i) pungi. Pentru fiecare oferta, aflati numarul minim de lei pe care Matei trebuie sa il plateasca pentru a obtine in total cel putin T pungi, apoi determinati costul minim dintre toate cele k oferte.
- Date de intrare
- Pe prima linie se citesc numerele naturale k si T. Urmeaza k linii, fiecare continand doua numere naturale a_i si b_i, reprezentand oferta i.
- Date de iesire
- Se afiseaza pe ecran costul minim (in lei) necesar pentru a obtine cel putin T pungi, folosind cea mai buna oferta.
- Restrictii
- 1 <= k <= 6, 1 <= T <= 100000, 1 <= a_i <= 1000, 0 <= b_i <= 1000
Exemple
Exemplul 1
Intrare
4 100 24 12 15 6 3 1 40 20
Iesire
72
Exemplul 2
Intrare
1 10 3 1
Iesire
8