题目描述

约翰的干草库存已经告罄，他打算为奶牛们采购 $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

输出格式

第1行：表示FJ获得至少H磅干草所需支付的最低成本的单个整数。

2 15 
3 2 
5 3

9

提示

FJ可以从第二个供应商购买三个包，总成本为9。