Payroll Calculation

A company finished a new piece of software one month earlier than planned. During the remaining month, it wants to focus on testing, so it will hire as many temporary testers as possible.

Each tester must be paid at least C won for the month in cash. The company's cash assets are given as counts for each denomination. Cash cannot be split, and exchanging a larger denomination into smaller denominations is not considered. Therefore, even when the total amount is large enough, the number of testers that can be hired depends on the actual bills and coins held.

For instance, if C is 5 and the company has one 1-won denomination and one 10-won denomination, it can pay one tester with the 10-won denomination, but the remaining 1 won cannot pay another tester.

The denominations are multiplicative: after sorting them in increasing order, each denomination divides the next larger denomination.

Given the company's cash and the minimum monthly wage, compute the maximum number of testers that can be hired.

The first line contains two integers N and C, the number of denomination types and the minimum wage. (1 <= N <= 20, 1 <= C <= 100,000,000)

Each of the next N lines contains two integers V and B, meaning that the company has B cash items of value V. (1 <= V <= 100,000,000, 1 <= B <= 1,000,000)

Print the maximum number of testers that can be hired.