Farmer John は物資が不足し始めており、牛のために $H$ $(1 \le H \le 50,000)$ ポンドの干し草を購入する必要があります。

彼は $1,\ldots,N$ と番号が付けられた $N$ $(1 \le N \le 100)$ 軒の干し草の供給業者を知っています。業者 $i$ は $P_{i}$ $(1 \le P_{i} \le 5,000)$ ポンドの干し草を含む包みを $C_{i}$ $(1 \le C_{i} \le 5,000)$ ドルで販売します。各業者の包みの在庫は無制限であり、包みは丸ごと購入しなければなりません。

少なくとも $H$ ポンドの干し草を購入するための最小費用を求め、FJ を助けてください。

入力

• 1 行目：空白で区切られた 2 つの整数 $N$ と $H$。
• $2,\ldots,N+1$ 行目：$i+1$ 行目には空白で区切られた 2 つの整数 $P_{i}$ と $C_{i}$ が与えられます。

出力

• 1 行目：FJ が少なくとも $H$ ポンドの干し草を得るために支払う最小費用を表す整数。

入出力例

入力 1

2 15
3 2
5 3

出力 1

9

注記

FJ は 2 番目の業者から包みを 3 個購入でき、その合計費用は 9 です。

問題作成者：Neal Wu，2007