logo AlgoBeat OnlineJudge
登录 注册

#102014. [BZOJ 2014] [Usaco2010 Feb]Chocolate Buying

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: 匿名

题目描述

贝西和其他奶牛们都喜欢巧克力,所以约翰准备买一些送给她们。奶牛巧克力专卖店里有 种巧克力,每种巧克力的数量都是无限多的。每头奶牛只喜欢一种巧克力,调查显示,有 头奶牛喜欢第 种巧克力,这种巧克力的售价是

约翰手上有 元预算,怎样用这些钱让尽量多的奶牛高兴呢?下面举个例子:假设约翰有 元钱,商店里有 种巧克力:

显然约翰不会去买第 种巧克力,因为他钱不够,不过即使它降价到 ,也不该选择它,因为这样只会让一头奶牛高兴,实在太浪费了。最好的买法是:第 种买 块,第 种买 块,第 种买 块,第 种买 块,正好用完 元,可以让 头牛高兴。

输入格式

第一行:两个用空格分开的整数:

第二行到 行:第 行,是两个用空格分开的整数:

输出格式

第一行:一个整数,表示最多可以让几头奶牛高兴。

样例

样例输入 #1

5 50
5 3
1 1
10 4
7 2
60 1

样例输出 #1

8

数据范围与提示

对于 的数据,

Silver