Farmer John is running out of supplies and needs to purchase $H$ $(1 \le H \le 50,000)$ pounds of hay for his cows.

He knows $N$ $(1 \le N \le 100)$ hay suppliers conveniently numbered $1,\ldots,N$. Supplier $i$ sells packages that contain $P_{i}$ $(1 \le P_{i} \le 5,000)$ pounds of hay at a cost of $C_{i}$ $(1 \le C_{i} \le 5,000)$ dollars. Each supplier has an unlimited number of packages available, and the packages must be bought whole.

Help FJ by finding the minimum cost necessary to purchase at least $H$ pounds of hay.

Input

• Line 1: Two space-separated integers: $N$ and $H$
• Lines $2,\ldots,N+1$: Line $i+1$ contains two space-separated integers: $P_{i}$ and $C_{i}$

Output

• Line 1: A single integer representing the minimum cost FJ needs to pay to obtain at least $H$ pounds of hay.

Examples

Input 1

2 15
3 2
5 3

Output 1

9

FJ can buy three packages from the second supplier for a total cost of 9.

Problem credits: Neal Wu, 2007