6014: BZOJ2014：[Usaco2010 Feb]Chocolate Buying

Memory Limit：64 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

    贝西和其他奶牛们都喜欢巧克力，所以约翰准备买一些送给她们。奶牛巧克力专卖店里 有N种巧克力，每种巧克力的数量都是无限多的。每头奶牛只喜欢一种巧克力，调查显示， 有Ci头奶牛喜欢第i种巧克力，这种巧克力的售价是P。     约翰手上有B元预算，怎样用这些钱让尽量多的奶牛高兴呢？下面举个例子：假设约翰 有50元钱，商店里有S种巧克力：

  巧克力品种     单价 高兴的奶牛数量
    1
    2
    3
    4
    5 		    5
    1
    10
    7
    60 		    3
    1
    4
    2
    1
     

    显然约翰不会去买第五种巧克力，因为他钱不够，不过即使它降价到50，也不该选择 它，因为这样只会让一头奶牛高兴，实在太浪费了。最好的买法是：第二种买1块，第一种 买3块，第四种买2块，第三种买2块，正好用完50元，可以让1+3+2+2=8头牛高兴。

输入格式

  第一行：两个用空格分开的整数：N和B，1<=N≤100000，1≤B≤10^18   第二行到N+1行：第i+l行，是两个用空格分开的整数：Pj和Ci，1≤Pi，Ci≤10^18

输出格式

  第一行：一个整数，表示最多可以让几头奶牛高兴

样例输入

5 50
53
11
10 4
7 2
60 1

样例输出

8

提示

没有写明提示

题目来源

Silver

加入题单

上一题 下一题 算法标签：