Chocolate Buying
暂无测试数据。
题目描述
贝西和其他奶牛们都喜欢巧克力,所以约翰准备买一些送给她们。奶牛巧克力专卖店里
有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
信息
- 难度
- 10
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 0
- 通过率
- 0%
- 上传者