The Splitting Club

The ACM (All Can Meet) club was founded to bring together people of all ages so that they could sit together, share their life experiences, and benefit one another. The club became so popular that gathering every member in one place at one time grew practically impossible, so the club decided to split its members into smaller sections. To keep the sections balanced, the director imposed three requirements:

1. All members of the same age must belong to the same section.
2. Every member must belong to exactly one section.
3. Within each section, the largest number of members sharing a single age must be at most $R$ times the smallest number of members sharing a single age. This value $R$, called the splitting factor, is a rational number with $1.0 \le R \le 2.0$.

The third requirement prevents a section from containing an age group so much smaller than the others that its members feel out of place.

For example, write [n, m] for a group of $n$ members who are $m$ years old. In the section {[10, 50], [6, 45], [70, 12], [43, 23]} the largest age group has 70 members and the smallest has 6, so with $R = 2.0$ this section violates requirement 3 because $70 / 6 > 2.0$. However, it can be split into the two sections {[10, 50], [6, 45]} and {[70, 12], [43, 23]}, each of which satisfies all three requirements.

Given the splitting factor $R$ and the list of members, find the minimum possible number of sections.

The input contains several test cases. The first line of each test case contains an integer $K$ and a rational number $R$, where $K$ is the number of distinct ages in the club ($1 \le K \le 120$) and $R$ is the splitting factor ($1.0 \le R \le 2.0$). Each of the next $K$ lines contains two integers $N$ and $M$, meaning that the club has $N$ members who are $M$ years old ($1 \le N \le 10000$ and $1 \le M \le 120$); every age is distinct. The input ends with a line containing $K = 0$ and $R = 0.0$, which must not be processed.

The input values are chosen so that any rounding error in the internal binary representation of $R$ will not affect the answer.

For each test case, print a single line containing the minimum number of sections that satisfy all three requirements.