你正在与兹梅·戈里尼奇(Zmei Gorynich)战斗——兹梅·戈里尼奇是斯拉夫神话中的凶猛怪物,一种巨大的龙状多头爬行动物!
最初 Zmei Gorynich 有 $$$x$$$ 头。你可以造成 $$$n$$$ 类型的打击。如果你进行第 $$$i$$$ 类型的打击,你会将 Gorynich 的头数减少 $$$min(d_i, curX)$$$,其中 $$$curX$$$ 是当前的头数。但如果在这一击之后兹梅·戈里尼奇至少有一个头,他就会长出$$$h_i$$$新头。如果 $$$curX = 0$$$ 则 Gorynich 被击败。
你可以以任意顺序进行任意次数的每次打击。
例如,如果$$$curX = 10$$$、$$$d = 7$$$、$$$h = 10$$$,则头数变为$$$13$$$(你砍掉$$$7$$$头,但Zmei会长出$$$10$$$新头),但如果$$$curX = 10$$$、$$$d = 11$$$,$$$h = 100$$$,则正面数量变为 $$$0$$$,Zmei Gorynich 被视为失败。
计算击败Zmei Gorynich的最少打击次数!
您必须回答 $$$t$$$ 独立查询。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) – 查询数量。
每个查询的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 100$$$, $$$1 \le x \le 10^9$$$) — 分别是可能的打击类型数量和 Zmei 最初拥有的头部数量。
每个查询的以下 $$$n$$$ 行包含您可以处理的打击类型的描述。第 $$$i$$$ 行包含两个整数 $$$d_i$$$ 和 $$$h_i$$$ ($$$1 \le d_i, h_i \le 10^9$$$) — 第 $$$i$$$ 打击的描述。
输出
对于每个查询,打印击败 Zmei Gorynich 所需的最少打击次数。
如果无法击败 Zmei Gorynuch,则打印 $$$-1$$$。
示例
输入 #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
输出 #1
2 3 -1
注意
在第一个查询中,您可以进行第一次打击(之后正面数量变为 $$$10 - 6 + 3 = 7$$$),然后进行第二次打击。
在第二个查询中,你只进行了三次第一击,Zmei 就被击败了。
在第三个查询中,您无法击败 Zmei Gorynich。也许说服它停止战斗更好?