The Splitting Club

Interview

Time limit1sMemory limit128 MB

Summary

Given distinct ages with member counts and a ratio R, partition all age groups into the fewest contiguous sections where the max count in a section is at most R times the min count.

Level: Medium6 of 10
Topics: Greedy, Two pointers, Sorting, Intervals
Solved: No attempts yet

Problem

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:

All members of the same age must belong to the same section.
Every member must belong to exactly one section.
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.

Input

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.

Output

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

Examples3

Example 1

Input

Expected output

3
3

Example 2
Input
```
1 1.5
5 10
0 0.0
```
Expected output
```
1
```
Example 3
Input
```
6 2.0
5 1
6 2
7 3
8 4
9 5
10 6
0 0.0
```
Expected output
```
1
```