Enunț
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ța
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 naturale 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
Fișierul de ieșire cafea.out
va conține pe prima linie un număr natural, reprezentând suma maximă care îi rămâne lui Algorel după ce umple plasa cu cafea.
Restricții și precizări
1 ≤ K ≤ 1 000 000 000
1 ≤ S ≤ 1 000 000 000
1 ≤ N ≤ 100 000
C
i
∈ [1, 100 000]
, pentru1 ≤ i ≤ N
P
i
∈ [1, 100 000]
, pentru1 ≤ i ≤ N
Exemplu:
cafea.in
1000 200 4 500 85 600 45 250 35 1000 1000
cafea.out
94
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.