P2376 [USACO05OCT] Allowance S / [USACO09OCT] Allowance G

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.

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)$.

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

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.