← 返回题目列表

Codeforces · 1217/B

B. 兹梅·戈里尼奇

中文机器翻译题面 查看原题

你正在与兹梅·戈里尼奇(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。也许说服它停止战斗更好?