时空限制

1S/512M

题目描述

你正在为好朋友挑选生日礼物。为了给他一个巨大的惊喜，你希望送出的礼物大礼包总“心意值”能够大于 $X$ 点。

目前礼品店里有 $n$ 件不同的候选礼物。第 $i$ 件礼物的基础价值为 $V_i$，它的惊喜度为 $P_i$。根据你的计算，如果送出这件礼物，它能为朋友带来 $V_i \times P_i$ 点的心意值。如果你同时送出多件礼物，它们带来的心意值将会完美累加。

为了方便包装，你希望购买最少数量的礼物来达到目标心意值。你可以自由挑选购买哪些礼物，但每件礼物只有一份（即最多只能购买一次）。

请计算并输出你最少需要购买几件礼物。如果把店里所有的 $n$ 件礼物全部买下也无法达到目标心意值，请输出 -1。

格式

输入格式

第一行包含两个整数 $n$ 和 $X$，具体含义见题目描述。

接下来 $n$ 行，每行包含两个整数 $V_i$ 和 $P_i$，分别表示第 $i$ 件礼物的基础价值和惊喜度。

输出格式

输出一行一个整数，表示最少需要购买的礼物件数。如果所有礼物全部买下也无法达到目标，请输出 -1。

样例

样例输入 #1

3 5000
50 40
100 20
80 50

样例输出 #1

2

样例解释 #1

根据给定的礼物属性，每件礼物能提供的心意值如下：

• 第 1 件：$50 \times 40 = 2000$ 点心意值；
• 第 2 件：$100 \times 20 = 2000$ 点心意值；
• 第 3 件：$80 \times 50 = 4000$ 点心意值。

选择同时购买第 $3$ 件和第 $1$ 件礼物，总心意值将达到 $4000 + 2000 = 6000$ 点，满足 $6000 > 5000$ 的条件，能够给朋友带来足够的惊喜。 因此，最少需要购买 $2$ 件礼物。

数据规模

对于 $100\%$ 的数据，$1 \leq n \leq 1000$，$1 \leq X \leq 10^7$，$1 \leq V_i \leq 100$，$0 \leq P_i \leq 100$。