Fişierul intrare/ieşire:cafea.in, cafea.outSursăad-hoc
AutorVictor ManzAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.3 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

cafea.incafea.out
1000 200 4
500 85
600 45
250 35
1000 1000
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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici