== include(page="template/taskheader" task_id="cafea") ==
Poveste și cerință...
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.
h2. 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.
h2. Date de intrare
Fișierul de intrare $cafea.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $cafea.out$ ...
Î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.
h2. 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$
h2. Exemplu
table(example).
|_. cafea.in |_. cafea.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1000 200 4
500 85
600 45
250 35
1000 1000
| 94
|
h3. 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.
== include(page="template/taskfooter" task_id="cafea") ==
