题目描述

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

输出格式

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

输入输出样例

2 15 
3 2 
5 3

9

说明/提示

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

GESPOJ 可见测试数据

以下数据是本题实际评测数据的一部分。

1 1
1055 212

212

7 7624
1143 1969
4734 2489
685 2558
762 615
599 2322
4418 2248
2462 2490

4496