Allowance

Time limit1sMemory limit128 MB

Summary

Given coin denominations where each divides the next and bounded supplies, find the maximum number of weeks you can pay at least C each week.

Level: Hard8 of 10
Topics: Greedy, Sorting, Implementation, Math
Solved: No attempts yet

Problem

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

Input

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.

Output

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

Hint

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.

Examples3

Example 1
Input
```
3 6
10 1
1 100
5 120
```
Expected output
```
111
```
Example 2
Input
```
1 5
5 10
```
Expected output
```
10
```
Example 3
Input
```
1 3
5 4
```
Expected output
```
4
```