Problem Description

On a certain planet on August 31st, Takahashi, a student on this planet, noticed something. Despite the summer vacation ending today, he hasn't completed any of his homework!

He has $ T $ minutes left until the homework deadline. Takahashi has $ N $ assignments to complete. It takes Takahashi $ A_i $ minutes to solve the $ i $-th assignment, but he can copy it from his friend Aoki, which would take $ B_i $ minutes. However, copying homework from a friend is not a good thing to do, so Takahashi wants to copy as little as possible.

Output the minimum number of assignments Takahashi needs to copy in order to finish all his homework before the deadline. If it's impossible to finish all the homework even by copying all of them, output -1 instead.

Input Format

The input is given from the standard input in the following format:

$ N $ $ T $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_N $ $ B_N $

• The first line contains two integers $N\ (1\ ≦\ N\ ≦\ 10^5),\ T\ (0\ ≦\ T\ ≦\ 10^9)$ separated by a space. This indicates that there are $ N $ assignments and $ T $ minutes left until the deadline.
• The next $ N $ lines contain the time information for the assignments. The $i\ (1\ ≦\ i\ ≦\ N)$-th line contains two integers $A_i,\ B_i\ (0\ ≦\ B_i\ <\ A_i\ ≦\ 10^4)$ separated by a space. This indicates that it takes Takahashi $ A_i $ minutes to solve the $ i $-th assignment and $ B_i $ minutes if he copies it. Note that $B_i\ <\ A_i$.

Output Format

Output the minimum number of assignments Takahashi needs to copy to finish all his homework within $ T $ minutes on one line. If it's impossible to finish all the homework within $ T $ minutes even by copying all of them, output -1 instead. End the output with a newline.

Sample Input and Output

Sample Input #1

5 7
1 0
3 0
5 0
2 0
4 0

Sample Output #1

2

Sample Input #2

1 1000000000
5 0

Sample Output #2

0

Sample Input #3

1 0
100 99

Sample Output #3

-1

Sample Input #4

3 11
5 2
6 4
7 3

Sample Output #4

2

Sample Input #5

6 92
31 4
15 9
26 5
35 8
97 9
32 3

Sample Output #5

3

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $B_i\ =\ 0$, you will be awarded $ 30 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 70 $ points.

Sample Explanation 1

For example, if he copies the 2nd and 3rd assignments, he can finish all the homework in $ 7(=1+0+0+2+4) $ minutes.

Sample Explanation 2

He can finish the homework on time without copying.

Sample Explanation 3

It's impossible to finish the homework on time even if he copies it.

见题面 Input 部分

见题面 Output 部分