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번째 줄: 공백으로 구분된 두 정수 $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