Fișierul intrare/ieșire	cafea.in, cafea.out	Sursă	ad-hoc
Autor	Victor Manz	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	1.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Cafea

Algorel a primit de la părinți o sumă de bani, S și o plasă în care încap K grame de cafea. Algorel trebuie să meargă la piață și să cumpere suficientă cafea încât să umple plasa. Pe de altă parte, părinții nu îi cer înapoi restul. Dacă va reuși să umple plasa, va putea păstra diferența de bani dintre suma primită S și costul total al cafelei achiziționate. Dacă nu va reuși să umple plasa, atunci nu va rămâne cu niciun ban.

La piață există N comercianți care vând cafea. Fiecare dintre aceștia are o cantitate de C _i grame de cafea pe care o vinde cu prețul total de P _i lei (1 ≤ i ≤ N). Comercianții nu au monede mai mici de 1 leu, așa că, în cazul în care clientul cumpără o cantitate de cafea al cărei preț nu este un număr întreg, acesta va plăti suma rotunjită la cea mai apropiată valoare întreagă mai mare sau egală cu valoarea datorată. De exemplu, dacă un comerciant vinde 1000 de grame de cafea la prețul de 25 de lei și un client vrea să cumpere 250 de grame, atunci acesta va plăti 7 lei, deși suma datorată era de 6,25 lei.

Cerință

Ajutați-l pe Algorel să rămână cu o sumă cât mai mare de bani, scriind un program care face acest calcul pe baza datelor corespunzătoare comercianților.

Date de intrare

Fișierul de intrare cafea.in va conține pe prima linie, separate prin câte un spațiu numerele K, S și N corespunzătoare capacității plasei, sumei pe pare o primește de la părinți și numărului de vânzători. Pe următoarele N linii se vor afla datele corespunzătoare comercianților: pe linia i + 1 se vor afla numerele naturale C _i și P _i reprezentând cantitatea maximă de cafea pe care o vinde comerciantul numărul i și prețul total cerut de acesta.

Date de ieșire

În fișierul de ieșire cafea.out se va scrie un singur număr natural, reprezentând suma maximă care îi rămâne lui Algorel după ce umple plasa cu cafea.

Restricții

• 1 ≤ K ≤ 1 000 000 000
• 1 ≤ S ≤ 1 000 000 000
• 1 ≤ N ≤ 100 000
• 1 ≤ C _i ≤ 100 000, pentru 1 ≤ i ≤ N
• 1 ≤ P _i ≤ 100 000, pentru 1 ≤ i ≤ N

Exemplu

Explicație

Algorel va cumpăra toată cafeaua vândută de comercianții cu numerele de ordine 2 și 3, cheltuind astfel 45 + 35 = 80 de lei pentru 600 + 250 = 850 de grame de cafea. Pentru a umple plasa, va mai achiziționa 150 de grame de cafea de la primul producător. Prețul acestei cantități este de 25,5 lei, care se rotunjește la 26 lei. Prin urmare suma totală pe care o plătește Algorel este de 106 de lei. Îi vor rămâne 94 lei.