A352. 歌曲压缩
编程题
普及+/提高
知识点
题目描述
Ivan的电话里有$n$首歌。第$i$首歌的大小是$a_i$字节。Ivan还有一个闪存驱动器，最多可容纳$M$字节。
最初，他的闪存驱动器是空的。
伊凡想把$N$首歌全部复制到闪存驱动器。
他能压缩歌曲。如果他压缩第$i$首歌，第$i$首歌的大小将从$a_i$减少到$b_i$字节$(bi<ai)$。
Ivan可以压缩歌曲的任何子集（可能是空的），并将所有歌曲复制到他的闪存驱动器（如果它们的大小总和最多为$m$）。
他可以压缩歌曲的任何子集（不一定是连续的）。
Ivan希望找到他需要压缩的最少歌曲数量，以使所有歌曲都适合驱动器（即大小之和小于或等于$m$）。
最初，他的闪存驱动器是空的。
伊凡想把$N$首歌全部复制到闪存驱动器。
他能压缩歌曲。如果他压缩第$i$首歌，第$i$首歌的大小将从$a_i$减少到$b_i$字节$(bi<ai)$。
Ivan可以压缩歌曲的任何子集（可能是空的），并将所有歌曲复制到他的闪存驱动器（如果它们的大小总和最多为$m$）。
他可以压缩歌曲的任何子集（不一定是连续的）。
Ivan希望找到他需要压缩的最少歌曲数量，以使所有歌曲都适合驱动器（即大小之和小于或等于$m$）。
输入格式
输入的第一行包含两个整数$n$ (Ivan手机上的歌曲数)和$m$(Ivan闪存驱动器的容量)$1$≤n≤$10^5$，$1$≤m≤$10^9$
接下来的$n$行包含两个整数：第$i$行包含两个整数$a_i$和$b_i$ (1≤ $a_i$，$b_i$≤$10^9$，$a_i$>$b_i)$-第$i$首歌的初始大小和压缩后第$i$首歌的大小。
接下来的$n$行包含两个整数：第$i$行包含两个整数$a_i$和$b_i$ (1≤ $a_i$，$b_i$≤$10^9$，$a_i$>$b_i)$-第$i$首歌的初始大小和压缩后第$i$首歌的大小。
输出格式
如果无法以所有歌曲都适合闪存驱动器的方式压缩歌曲的子集，请打印“-1”。否则，打印要压缩的最少歌曲数。
输入输出样例
输入 #1
4 21 10 8 7 4 3 1 5 4
输出 #1
2