← 返回题目列表

Codeforces · 1015/C

C. 歌曲压缩

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

Ivan 的手机上有 $$$n$$$ 歌曲。第 $$$i$$$ 歌曲的大小为 $$$a_i$$$ 字节。 Ivan 还有一个闪存驱动器,总共最多可容纳 $$$m$$$ 字节。最初,他的闪存驱动器是空的。

Ivan 想要将所有 $$$n$$$ 歌曲复制到闪存驱动器。他可以压缩歌曲。如果他压缩第 $$$i$$$ 歌曲,则第 $$$i$$$ 歌曲的大小从 $$$a_i$$$ 减少到 $$$b_i$$$ 字节 ($$$b_i < a_i$$$)。

Ivan 可以压缩歌曲的任何子集(可能为空),并将所有歌曲复制到他的闪存驱动器(如果它们的大小总和最多为 $$$m$$$)。他可以压缩歌曲的任何子集(不一定是连续的)。

Ivan 想要找到他需要压缩的最小歌曲数量,以便他的所有歌曲都适合驱动器(即它们的大小总和小于或等于 $$$m$$$)。

如果无法复制所有歌曲(即使 Ivan 压缩了所有歌曲),则打印“-1”。否则打印 Ivan 需要压缩的最小歌曲数。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5, 1 \le m \le 10^9$$$) — Ivan 手机上的歌曲数量和 Ivan 闪存驱动器的容量。

接下来的 $$$n$$$ 行每行包含两个整数:第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$, $$$a_i > b_i$$$) — 第 $$$i$$$ 歌曲的初始大小和压缩后第 $$$i$$$ 首歌曲的大小。

输出

如果无法以所有歌曲都适合闪存驱动器的方式压缩歌曲子集,请打印“-1”。否则打印要压缩的最小歌曲数。

示例

输入 #1

4 21
10 8
7 4
3 1
5 4

输出 #1

2

输入 #2

4 16
10 8
7 4
3 1
5 4

输出 #2

-1

注意

在第一个示例中,Ivan 可以压缩第一首和第三首歌曲,因此在这些移动之后,大小之和将等于 $$$8 + 7 + 1 + 5 = 21 \le 21$$$。 Ivan 还可以压缩第一首和第二首歌曲,那么大小之和将等于 $$$8 + 4 + 3 + 5 = 20 \le 21$$$。请注意,压缩任何一首歌曲不足以复制闪存驱动器上的所有歌曲(例如,压缩第二首歌曲后,大小总和将等于 $$$10 + 4 + 3 + 5 = 22 > 21$$$)。

在第二个示例中,即使 Ivan 压缩了所有歌曲,大小总和也将等于 $$$8 + 4 + 1 + 4 = 17 > 16$$$。