题目描述

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

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

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

输入格式

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

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

输出格式

最小的开销．

样例

输入样例

2 15
3 2
5 3

输出样例

9

提示

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