Rezolvare PBinfo #3739

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 Ci grame de cafea pe care o vinde cu preţul total de Pi 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 Ci şi Pi 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
• Ci ∈ [1, 100 000], pentru 1 ≤ i ≤ N
• Pi ∈ [1, 100 000], pentru 1 ≤ 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.