Rezolvare PBinfo #4010

Cerința

Moș Crăciun pregătește cadourile pentru acest an. El trebuie să dea cadouri identice la n copii. Pentru aceasta, a vizitat m magazine (posibil online) și pentru fiecare magazin a aflat prețul cadoului în acel magazin și numărul de cadouri disponibile în acel magazin.

Determinati suma minimă necesară pentru a cumpăra cele n cadouri necesare. Dacă nu se pot cumpăra cele n cadouri afișați mesajul imposibil.

Date de intrare

Programul citește de la tastatură numerele n m, iar apoi m perechi numere naturale p c, reprezentând prețul și cantitatea de cadouri disponibile în cele n magazine.

Date de ieșire

Programul va afișa pe ecran suma totală necesară S sau mesajul imposibil.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ 100
• 0 ≤ c ≤ 100
• 1 ≤ p ≤ 100

Exemplu:

Intrare

5 3
2 1
4 5
3 2

Ieșire

16

Explicație

Moș Crăciun va cumpăra un cadou cu prețul 2, două cu prețul 3 și două cu prețul 4.