B-Zmei Gorynich

题目描述

你正在与 Zmei Gorynich 战斗——这是斯拉夫神话中的一只凶猛怪兽，一条拥有多颗头颅的巨型龙！

最初，Zmei Gorynich 有 $x$ 个头。你可以使用 $n$ 种不同类型的攻击。如果你使用第 $i$ 种攻击，会使 Gorynich 的头数减少 $min(d_i, curX)$，其中 $curX$ 表示当前的头数。但如果这次攻击后 Zmei Gorynich 仍然至少有一个头，他会再长出 $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$ 行，每行包含两个整数 $d_i$ 和 $h_i$（$1 \le d_i, h_i \le 10^9$），表示第 $i$ 种攻击的描述。

输出格式

对于每个询问，输出击败 Zmei Gorynich 所需的最少攻击次数。

如果无法击败 Zmei Gorynich，输出 $-1$。

输入输出样例 #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

输入 #2

4
1 1
1 1
1 1
1 1000000000
1 1000000000
1 1
1 1000000000
1000000000 1000000000

输出 #2

1
1
-1
1

说明/提示

在第一个询问中，你可以先使用第一种攻击（此时头数变为 $10 - 6 + 3 = 7$），然后再使用第二种攻击。

在第二个询问中，你只需连续使用第一种攻击三次，Zmei 就会被击败。

在第三个询问中，你无法击败 Zmei Gorynich。也许劝他停止战斗会更好？