题目描述

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

输入描述

第1行输入N和H，之后N行每行输入一个Pi和Ci。

输出描述

最小的开销。

输入样例1

2 15
3 2
5 3

输出样例1

9

提示

FJ can buy three packages from the second supplier for a total cost of 9.