[USACO08NOV] Buying Hay S

题目描述

约翰的干草库存已经告罄，他打算为奶牛们采购 $H(1 \leq H \leq 50000)$ 磅干草。

他知道 $N(1 \leq N\leq 100)$ 个干草公司，现在用 $1$ 到 $N$ 给它们编号。第 $i$ 个公司卖的干草包重量为 $P_i (1 \leq P_i \leq 5,000)$ 磅，需要的开销为 $C_i (1 \leq C_i \leq 5,000)$ 美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。

帮助约翰找到满足需要的最小开销，即采购到至少 $H$ 磅干草。

输入格式

第 $1$ 行：两个整数： $N$ 与 $H$ ，以空格分隔。

第 $2$ 行至第 $N+1$ 行：其中第 $i+1$ 行包含两个整数： $P_i$ 与 $C_i$ ，以空格分隔。

输出格式

一个整数，表示 FJ 至少采购到 $H$ 磅干草所需的最少花费。

输入输出样例 #1

输入 #1

2 15 
3 2 
5 3 

输出 #1

9 

说明/提示

FJ 可以在第二家公司买 $3$ 包干草，共花费 $9$ 美元。