You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在神秘的地狱深处，有着一种神秘的犬类生物，据传这种生物长了 $x$ 个脑袋，并且具有强大的生命力。由于见过它的人全都下落不明，至今没有人知道它的真面目。

一位勇士为了斩杀这奇怪的生物，来到地狱一探究竟。勇士做了充足的准备，他在身上携带了 $n$ 种武器，每种武器每次可以击毙这种生物 $d_i$ 个头，但这种生物在这之后会吸收武器产生的能量，在长出 $h_i$ 个头。当它的头的数量小于等于 $0$ 时，它就会被击败（且不能重新长出头）。注意，每种武器可以无限次使用。

作为勇士的智囊团中的一员，你需要告诉勇士，他最少需要使用多少次武器才能击败这种生物。

输入格式

输入第一行包含两个整数 $n,x$​，分别表示勇士的武器种类数与生物头的数量。

之后 $n$ 行，每行给出 $d_i,h_i$。

输出格式

输出共一行，表示最少需要使用多少次武器。若不能击败，则输出 $-1$。

3 10
6 3
8 2
1 4

2

样例 1 解释

可以先使用一次第一个技能，生物还剩下个 $10-6+3=7$ 个头。第二次使用第二个技能，剩下 $7 - 8 = -1 < 0$ 个头，则直接被击败。

4 10
4 1
3 2
2 6
1 100

3

2 15
10 11
14 100

-1

其余样例见下发文件。 dog4.in
dog4.ans
dog5.in
dog5.ans

数据规模与约定

• 对于 $20\%$ 的数据，保证 $n = 1,x\le20$。
• 对于 $40\%$ 的数据，保证 $n \le 2,x \le 20$。
• 对于 $60\%$ 的数据，保证 $n \le 10$。
• 对于 $100\%$ 的数据，保证 $1 \le n \le 100,1 \le x,d_i,h_i \le 10^9$。