1030: 采购干草

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:179 通过:71

题目描述

约翰的干草库存已经告罄他打算为奶牛们采购H(1≤H≤50000)磅干草。
他知道N(1≤N≤100)个干草公司,现在用1到N给它们编号,第i个公司卖的干草包重量为P_i (1 <= P_i <= 5,000)。需要的开销为C_i (1 <= C_i <= 5,000)美元,每个干草公司的货源都十分充足.可以卖出无限多的干草包。
帮助约翰找到最小的开销来满足需要,即采购到至少H磅干草。

输入格式

1行输入NH.之后N行每行输入一个只和q.

输出格式

最小的开销。

输入样例 复制

2 15
3 2
5 3

输出样例 复制

9

数据范围与提示

约翰可以从第二个供应商那里购买三个软件包,总成本9