Allowance

As a reward for record milk production, Farmer John has decided to give Bessie a small weekly allowance.

Farmer John has coins in $N$ ($1 \le N \le 20$) different denominations, where each denomination evenly divides the next-larger denomination (that is, every larger denomination is a multiple of every smaller one).

Using these coins, he wants to pay Bessie at least a given amount $C$ ($1 \le C \le 100{,}000{,}000$) every week. Determine the maximum number of weeks Farmer John can pay Bessie an allowance of at least $C$.

• Line 1: Two space-separated integers $N$ and $C$.
• Lines 2 to $N+1$: Each line describes one denomination and contains its value $V$ ($1 \le V \le 100{,}000{,}000$) and the number of coins $B$ ($1 \le B \le 1{,}000{,}000$) of that denomination that Farmer John owns.

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

Farmer John can overpay Bessie with the single 10-cent coin for 1 week, then pay two 5-cent coins each week for 10 weeks, and finally pay one 1-cent coin and one 5-cent coin each week for 100 weeks, for a total of $1 + 10 + 100 = 111$ weeks.