Ран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