Problem 25380 --合照

25380: 合照

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 8  Solved: 3
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][180kb]

Description

 

问题描述:

       歌手SJM到幼儿园跟小朋友玩,他到达的时候小朋友已经争着积木玩了。小朋友都想要更多的积木砌一个自己喜欢的图形,砌完就可以和SJM合照。同时,SJM手上还有一些积木,他可以把手里的这些积木全部给一个小朋友,然后等该小朋友砌完后就可以收回所发的积木和该小朋友原先手里的积木。但SJM想知道他最多可以和多少个小朋友合照,你能帮助他吗?

输入格式:

输入第一行包括两个正整数NS,中间用空格隔开,其中1<=N<=1000,1<=S<=10000,表示一共有N位小朋友, SJM手上有S块积木。以下有N行,每行有两个正整数,ab(1<=a<=10^5,1<=b<=10^9),表示每个小朋友手上有的积木数量和还需要的积木数量。

输出格式:

输出SJM最多可以和多少个小朋友合照。

样例输入输出:

    输入样例1

输出样例1

2 2

1 4

2 1

2

    输入样例2

输出样例2

2 2

1 4

1 1

1

样例解释:

   样例1:有2个小朋友,SJM手里一开始有2块积木,第1个小朋友手里有1块积木,他还需要4块积木,第2个小朋友手里有2块积木,他还需要1块积木,SJM可以先满足第2个小朋友的需求,即给第2个小朋友1块积木,这样第2个小朋友就可以砌完图形,然后把所有的积木给SJM,这样SJM就有4块积木,此时可以满足第1个的需求,所有可以和2个小朋友合照。

   样例2SJM一开始只能满足第2个小朋友的需求,然后积木数量变为3,还是不能满足第1个小朋友的需求,所以最多只能和1个小朋友合照。

Input

Output

HINT

Source

[Submit][Status]