OI题库

【问题描述】          

ZZ市准备在绿博园举办一次花卉节。Dr.Kong接受到一个任务，要买一批花卉进行布置园林。

能投入买花卉的资金只有B元 (1 <= B <= 10^18) 。Dr.Kong决定做一个社会调查，统计一下市民们都喜欢哪种花卉，以便在有限的资金范围内，让更多的市民都能找到并标注一盆自己喜欢的花卉（一盆花只能一位市民标注）。  

经调查统计，市场上有N (1 <= N<=100,000)种不同类型的花卉，第i种花卉的价格是Pi(1 <= Pi <= 10^18) 。有Ci (1 <= Ci <= 10^18) 个市民喜欢。

你能帮助Dr.Kong计算一下，在不透支的情况下，如何购买花卉才能让更多的市民都能找到并标注一盆自己喜欢的花卉？  

例如：Dr.Kong 有 50块钱，有5种不同类型的花卉：

花卉类型             价格/盆                喜欢该类型花卉市民的人数

1                        5                              3

2                        1                              1

3                        10                             4

4                        7                              2

5                        60                             1

 

显然，Dr.Kong不能购买第5种类型的花卉,因为他不够钱。

下面的购买方案是最优的：

第1种花卉买3盆；第2种花卉买1盆；第3种花卉买2盆；第4种花卉买2盆。

总共花费：5*3+1*1+10*2+7*2=50，这样，Dr.Kong 最多能让3+1+2+2 =8 人满意。

输入格式：

第1行:   N  B

第2..N+1行:  Pi Ci   （i=1，2，....，N）。

输出格式：

一个整数，最多可以让多少市民满意。

输入样例                

5 50

5 3

1 1

10 4

7 2

60 1

输出样例          

8