Farmer John 的物資快用完了，需要為奶牛購買 $H$ $(1 \le H \le 50,000)$ 磅乾草。

他認識 $N$ $(1 \le N \le 100)$ 個乾草供應商，為方便起見編號為 $1,\ldots,N$。供應商 $i$ 出售每包包含 $P_{i}$ $(1 \le P_{i} \le 5,000)$ 磅乾草的包裝，每包價格為 $C_{i}$ $(1 \le C_{i} \le 5,000)$ 美元。每個供應商都有無限多包可供購買，而且必須整包購買。

請幫助 FJ 求出購買至少 $H$ 磅乾草所需的最低費用。

輸入格式

• 第 1 行：兩個以空格分隔的整數 $N$ 和 $H$。
• 第 $2,\ldots,N+1$ 行：第 $i+1$ 行包含兩個以空格分隔的整數 $P_{i}$ 和 $C_{i}$。

輸出格式

• 第 1 行：一個整數，表示 FJ 取得至少 $H$ 磅乾草需要支付的最低費用。

範例

輸入格式 1

2 15
3 2
5 3

輸出格式 1

9

說明

FJ 可以向第二個供應商購買三包，總費用為 9。

題目作者：Neal Wu，2007