Вы сражаетесь со Змеем Горынычем — со свирепым монстром из славянских легенд!
Изначально у Змея Горыныча $$$x$$$ голов. Вы можете наносить ему $$$n$$$ типов ударов. Если вы нанесете удар $$$i$$$-го типа, вы уменьшите количество голов Горыныча на $$$min(d_i, curX)$$$, где $$$curX$$$ — текущее количество голов. Но если после этого удара у Горыныча осталась хотя бы одна голова, у него отрастает $$$h_i$$$ новых голов. Если $$$curX = 0$$$, то Горыныч побежден.
Каждый удар можно наносить любое количество раз, сами удары можно наносить в любом порядке.
Например, если $$$curX = 10$$$, $$$d = 7$$$, $$$h = 10$$$, то после удара количество голов станет равным $$$13$$$ (вы отрубаете $$$7$$$ голов, но после этого у Горыныча отрастает $$$10$$$ новых), но если $$$curX = 10$$$, $$$d = 11$$$, $$$h = 100$$$, то после удара количество голов станет равным $$$0$$$ и Горыныч считается побежденным.
Посчитайте минимальное количество ударов для победы над Змеем Горынычем!
Вам нужно ответить на $$$t$$$ независимых запросов.
Первая строка содержит число $$$t$$$ ($$$1 \le t \le 100$$$) – количество запросов.
Первая строка каждого запроса содержит два числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 100$$$, $$$1 \le x \le 10^9$$$) — количество возможных типов ударов и изначальное количество голов Змея Горыныча соответственно.
Следующие $$$n$$$ строк содержат описания возможных ударов. $$$i$$$-я строка содержит два числа $$$d_i$$$ и $$$h_i$$$ ($$$1 \le d_i, h_i \le 10^9$$$) — описание $$$i$$$-го удара.
На каждый запрос выведите минимальное количество ударов для победы над Змеем Горынычем.
Если Змея Горыныча нельзя победить выведите $$$-1$$$.
3 3 10 6 3 8 2 1 4 4 10 4 1 3 2 2 6 1 100 2 15 10 11 14 100
2 3 -1
В первом запросе вы может нанести первый удар (после этого количество голов станет равно $$$10 - 6 + 3 = 7$$$), а затем нанести второй удар.
Во втором запросе вы можете нанести первый удар три раза подряд — и Горыныч побежден.
В третьем примере вы не можете победить Змея Горыныча.
