Mariuca
a primit de ziua ei un purcelus-pusculita. De atunci, ori de câte ori
are ceva bani marunti, îi pune în pusculita.
Azi tocmai a vazut cea mai frumoasa papusa Barbie. Dar din pacate Mariuca nu
stie daca banii din pusculita sunt suficienti pentru a o cumpara. Pentru a numara
banii, ar trebui sa sparga pusculita, dar… daca banii nu-s de-ajuns ramâne
si fara Barbie si fara pusculita.
Mariuca stie cât cântarea pusculita goala, de asemenea stie greutatea
fiecarui tip de moneda din pusculita si bineînteles stie cât cântareste
pusculita plina.
Cerinta
Scrieti
un program care sa o ajute pe Mariuca sa afle care este suma minima care s-ar
putea afla în pusculita.
Date de intrare
Fisierul
de intrare barbie.in contine
pe prima linie doua numere naturale separate prin spatiu GP
PP (GP reprezinta greutatea
pusculitei goale, iar PP greutatea
pusculitei pline). Pe cea de a doua linie se afla un numar natural N
care reprezinta numarul de tipuri de monede care s-ar putea afla în pusculita.
Urmatoarele N linii descriu cele
N tipuri de monede. Pe fiecare
dintre cele N linii sunt scrise
doua numere naturale V G (V
reprezinta valoarea monedei, iar G
reprezinta greutatea ei).
Date de iesire
Fisierul
de iesire barbie.out va
contine o singura linie pe care va fi scrisa suma minima care s-ar putea afla
în pusculita.
Restrictii si precizari
1 <= GP
<= PP <= 10000
1 <= N <= 500
1 <= V <= 50000, 1 <= G <=10000
Toate greutatile sunt exprimate în grame.
Greutatile si respectiv valorile monedelor nu sunt neaparat distincte.
Pentru toate datele de test exista solutie.