Description

As a reward for setting a milk production record, Farmer John decides to give Bessie a weekly allowance.

FJ has some coins, with $N (1 \le N \le 20)$ different denominations. Each denomination divides all larger denominations.

Using the given collection of coins, he wants to give Bessie at least $C (1 \le C \le 100000000)$ each week. Please compute the maximum number of weeks he can make such payments.

Input Format

Line $1$: Two space-separated integers: $N$ and $C$.

Lines $2$ to $N+1$: Each line contains two integers describing one coin denomination: the coin value $V (1 \le V \le 100,000,000)$ and the number of coins of that denomination $B (1 \le B \le 1,000,000)$.

Output Format

Line $1$: A single integer, the maximum number of weeks he can pay an allowance of at least $C$.

3 6
10 1
1 100
5 120

111

Hint

FJ can overpay Bessie with the one $10$-cent coin for $1$ week, then pay Bessie two $5$-cent coins for $10$ weeks and then pay Bessie one $1$-cent coin and one $5$-cent coin for $100$ weeks.