题目描述

约翰的干草库存已经告罄,他打算为奶牛们采购$\red{H(1≤}$$\red{H≤}$$\red{50000)}$磅干草,他知道$\red{N(1≤}$$\red{N≤}$$\red{100)}$个干草公司,现在用$\red{1}$到 $\red{N}$给它们编号。

第$\red{i}$个公司卖的干草包重量为$\red{Pi(1≤}$$\red{Pi≤}$$\red{5000)}$磅,需要的开销为$\red{Ci(l≤}$$\red{Ci≤}$$\red{5000)}$美元．每个干草公司的货源都十分 充足,可以卖出无限多的干草包．

帮助约翰找到最小的开销来满足需要,即采购到至少$\red{H}$磅干草 ．

输入格式

第$\red{1}$行输入$\red{N}$和$\red{H，}$

之后$\red{N}$行每行输入一个$\red{Pi}$和$\red{Ci}$．

输出格式

最小的开销．

样例

输入样例

2 15
3 2
5 3

输出样例

9

提示

$\red{FJ}$可以从第二个供应商那里购买三个包装，总成本为$\red{9}$美元。