1481: Скарбничка


Submit solution


Points:10
Time limit:1.0s
Memory limit:500M
Author:

Problem types

Ранiше були популярнi скарбнички у виглядi симпатичної свинки з отвором для вкидання монет. Денис має таку скарбничку i вона уже доволi важка. Зараз вiн планує придбати один iз необхiдних йому гаджетiв i, звiсно, виникає слушне запитання: чи достатньо коштiв мiстить його скарбничка? Дениса цiкавить мiнiмальна гарантована сума, яка може мiститися у скарбничцi. Вiн знає масу порожньої скарбнички E та масу скарбнички iз монетами F. Зрозумiло, що Денис знає, що його валюта має N рiзних номiналiв монет. Також вiн визначив для кожного номiналу монети її масу у грамах.

Складiть програму, яка визначить мiнiмальну суму грошей у скарбничцi Дениса.

Формат вхідних даних

Перший рядок мiстить два цiлих числа E, F (1 <= E, F <= 10000) - вага порожньої та заповненої скарбнички у грамах. Наступний рядок мiстить N (1 <= N <= 500)- кiлькiсть номiналiв монет у валютi Дениса. Далi iдуть N рядкiв, кожен з яких мiстить монету номiналом V (1 <= V <= 50000) та її масу W (1 <= W <= 10000).

Формат вихідних даних

Вивести мiнiмальну суму грошей у скарбничцi Дениса або -1, якщо її визначити неможливо.

Приклад вхідних даних

10 110
2
1 1
30 50

Приклад вихідних даних

60

Приклад вхідних даних

10 110
2
1 1
50 30

Приклад вихідних даних

100

Приклад вхідних даних

1 6
2
10 3
20 4

Приклад вихідних даних

-1

Comments

There are no comments at the moment.