問題文
某星 8 月 31 天。来自某个星球的高桥察觉到了一些事情。虽然今天暑假结束了,但是我的作业还没有完成呢!
只剩下做作业的时间了 还有 T 分钟。而高桥要做的功课就是 有 N 件。 让高桥解决i 作业 需要 A_i 分钟,但是通过抄写高桥的朋友青木解决的作业, 您也可以在 B_i 分钟内完成。然而,拍摄朋友的作业并不是一个好主意,因此高桥希望尽可能避免拍摄朋友的作业。
请输出高桥需要抄写的最少作业项目数,以便在时限内完成所有作业。但是,如果即使抄完所有作业也无法在规定时间内完成,
请输出 -1 。
入力
输入将以以下格式从标准输入提供。
N T A_1 B_1 A_2 B_2 : A_N B_N
- 1 第几行包含,2 整数 N (1 ≦ N ≦ 10^5), T (0 ≦ T ≦ 10^9) 用空格分隔。这是家庭作业 有 N 块,距离限制时间为 代表 T 分钟。
- 2 从线 N 行提供有关作业所需时间的信息。其中 当高桥解决 i (1 ≦ i ≦ N) 第几行包含,2 整数 A_i, B_i (0 ≦ B_i < A_i ≦ 10^4) 用空格分隔。这是i 作业时 复制需要 A_i 分钟。 表示需要 B_i 分钟。 请注意B_i < A_i 。 如果正确答案是满足
部分点
针对此问题设置了部分分数。
- B_i = 0 的数据集,30 点。 如果您正确回答
- 除了上述内容之外,如果答案对于没有附加约束的数据集是正确的, 70 点。 如果您正确回答
出力
T 高桥需要抄多少作业才能在几分钟内完成所有作业。
在 1 行输出。然而,即使你抄了所有的作业, T 如果您无法在几分钟内完成,请改为
输出 -1 。在输出末尾插入换行符。
入力例1
5 7 1 0 3 0 5 0 2 0 4 0
出力例1
2
例如, 如果你抄2 th 和 如果您选择第 3 作业 您可以在 7(=1+0+0+2+4) 分钟内完成所有作业。
入力例2
1 1000000000 5 0
出力例2
0
您可以在不抄作业的情况下满足时间限制。
入力例3
1 0 100 99
出力例3
-1
即使我抄作业,我也无法满足时间限制。
入力例4
3 11 5 2 6 4 7 3
出力例4
2
入力例5
6 92 31 4 15 9 26 5 35 8 97 9 32 3
出力例5
3