A263.歌曲压缩

普及+/提高

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Ivan的电话里有nn首歌。第ii首歌的大小是aia_i字节。Ivan还有一个闪存驱动器,最多可容纳MM字节。

最初,他的闪存驱动器是空的。
伊凡想把NN首歌全部复制到闪存驱动器。

他能压缩歌曲。如果他压缩第ii首歌,第ii首歌的大小将从aia_i减少到bib_i字节(bi<ai)(bi<ai)

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

他可以压缩歌曲的任何子集(不一定是连续的)。
Ivan希望找到他需要压缩的最少歌曲数量,以使所有歌曲都适合驱动器(即大小之和小于或等于mm)。

输入格式

输入的第一行包含两个整数nn (Ivan手机上的歌曲数)和mm(Ivan闪存驱动器的容量)11≤n≤10510^511≤m≤10910^9

接下来的nn行包含两个整数:第ii行包含两个整数aia_ibib_i (1≤ aia_ibib_i10910^9aia_i>bi)b_i)-第ii首歌的初始大小和压缩后第ii首歌的大小。

输出格式

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

输入输出样例

  • 输入#1

    4 21
    10 8
    7 4
    3 1
    5 4

    输出#1

    2
首页