← 返回题目列表

AtCoder · codefestival_2015_qualA_c

C. 8月31日

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

問題文

某星 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