#9356. [USACO08NOV] Buying Hay S 普及/提高−

约翰的干草库存已经告罄，他打算为奶牛们采购 磅干草。

他知道 个干草公司，现在用 到 给它们编号。第 公司卖的干草包重量为 磅，需要的开销为 美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。

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

第 行：两个整数： 与 ，以空格分隔。

第 行至第 行：其中第 行包含两个整数： 与 ，以空格分隔。

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

样例输入 1

2 15 
3 2 
5 3

样例输出 1

9

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