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


  • 0
    Artur_Kozyra2002
     commented on Oct. 15, 2020

    В другому прикладі з вхідних даних вага скарбнички 100г, є дві монети: номіналом 1 і вагою 1г, та номіналом 50 і 30г. Мінімальна сума грошей повинна бути 160, але у вихідних даних вона 100, або я щось не так зрозумів? В другому тесті також виводить WA з відповіддю 160, підозрюю, це той самий тест.


    • 1
      zvit
       commented on Oct. 15, 2020

      нас цікавить мінімальна сума і вона у другому прикладі рівна 100 - 100 монет вагою по 1г