题目描述

Ivan 的手机上有 $n$ 首歌曲，第 $i$ 首歌曲的大小为 $a_i$ 字节。他还有一个容量最多为 $m$ 字节的 U 盘，初始时 U 盘为空。

Ivan 想要把所有 $n$ 首歌曲都复制到 U 盘上。他可以对歌曲进行压缩。如果他压缩第 $i$ 首歌曲，那么该歌曲的大小会从 $a_i$ 字节变为 $b_i$ 字节（$b_i < a_i$）。

Ivan 可以选择任意一些（可能为空）歌曲进行压缩，只要所有歌曲的总大小不超过 $m$，就可以全部复制到 U 盘上。被压缩的歌曲不需要连续。

Ivan 想知道，最少需要压缩多少首歌曲，才能使所有歌曲都能放进 U 盘（即所有歌曲的总大小不超过 $m$）。

如果即使压缩所有歌曲也无法全部放进 U 盘，请输出 “-1”。否则请输出最少需要压缩的歌曲数。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^5, 1 \le m \le 10^9$），分别表示 Ivan 手机上的歌曲数量和 U 盘的容量。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9, a_i > b_i$），分别表示第 $i$ 首歌曲原始的大小和压缩后的大小。

输出格式

如果无论如何都无法将所有歌曲放进 U 盘，输出 “-1”。否则输出最少需要压缩的歌曲数。

说明/提示

在第一个样例中，Ivan 可以压缩第 1 首和第 3 首歌曲，这样所有歌曲的总大小为 $8 + 7 + 1 + 5 = 21 \le 21$。也可以压缩第 1 首和第 2 首歌曲，此时总大小为 $8 + 4 + 3 + 5 = 20 \le 21$。注意，仅压缩一首歌曲无法满足要求（例如只压缩第 2 首，总大小为 $10 + 4 + 3 + 5 = 22 > 21$）。

在第二个样例中，即使将所有歌曲都压缩，总大小也为 $8 + 4 + 1 + 4 = 17 > 16$，无法全部放进 U 盘。

由 ChatGPT 4.1 翻译

样例

4 21
10 8
7 4
3 1
5 4

2

4 16
10 8
7 4
3 1
5 4

-1