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.

Timp maxim de executie/test: 0.1 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com