A devenit o adevărată artă să alcătuieşti un meniu care să fie bogat dar să conţină cât mai puţine calorii. Fiecare produs are înscris pe el procentul de grăsimi pe care îl conţine şi numărul de calorii. Din păcate acest lucru nu se întâmplă şi la piaţă. Văzând aceasta, un ţăran inventiv, care oferă spre vânzare un număr de n produse, a făcut un mic calcul şi a determinat, pentru fiecare dintre produsele oferite spre vânzare, numărul de calorii pe care le conţine întreaga cantitate din produsul respectiv. Ţăranul a scris pe câte o etichetă numerele astfel determinate şi a pus fiecare etichetă lângă produsul corespunzător, având grijă ca după fiecare vânzare să corecteze în mod corespunzător numărul înscris pe etichetă.
O gospodină ce dispune de o anumită sumă de bani S pentru cumpărături, doreşte să cumpere produse de la acel ţăran astfel încât să cheltuiască întreaga sumă S de care dispune, dar să ducă acasă cât mai multe calorii. Gospodinei îi este indiferent ce produse cumpără şi în ce cantităţi, scopul fiind ca produsele cumpărate să conţină în totalitate cel mai mare număr de calorii.
Cerinţă
Să se determine cantitatea maximă de calorii pe care gospodina a reuşit să o cumpere.
Date de intrare
Fişierul de intrare calorii.in va conţine pe prima linie un număr natural n, reprezentând numărul de produse. Fiecare dintre următoarele n linii va conţine câte două valori naturale, reprezentând numărul de calorii determinat de ţăran pentru produs şi cât costă întreaga cantitate din produsul respectiv. Ultima linie a fişierului de intrare va conţine o valoare naturală S reprezentând suma de care dispune gospodina pentru cumpărături.
Date de ieşire
Fişierul de ieşire calorii.out va conţine pe prima linie o valoare reală cu 4 zecimale reprezentând numărul maxim de calorii conţinute în produsele cumpărate de gospodină.
Restricţii
• 1 ≤ n ≤ 10000
• 1 ≤ S ≤ 2000000000
• Numărul de calorii şi preţurile sunt valori naturale <=30000
• Rezultatul afişat este considerat corect dacă primele 3 zecimale afişate sunt corecte, adică eroarea este mai mică decât 10-3
Exemple
calorii.in
calorii.out
Explicaţii
5
100 5
300 4
150 7
700 2
500 20
30
1585.7143
Rezultatul se obţine prin cumpărarea integrală a produselor 2, 4 şi 5 şi a 57.1428571% din produsul 3. Prin calcul se observă faptul că:
300+700+500+57.1428571*150/100 = 1585.71428565
Se observă faptul că primele 3 zecimale sunt corecte, cea de a patra fiind rotunjită automat la afişare.