Ран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 \le E, F \le 10000)~ - вага порожньої та заповненої скарбнички у грамах.

Наступний рядок мiстить ~N~ ~(1 \le N \le 500)~- кiлькiсть номiналiв монет у валютi Дениса.

Далi iдуть ~N~ рядкiв, кожен з яких мiстить монету номiналом ~V~ ~(1 \le V \le 50000)~ та її масу ~W~ ~(1 \le W \le 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