400401: GYM100162 H Temperature

It is autumn in Berland and that means another flu epidemic is coming.

The teacher gave each of n students a thermometer and asked to measure their temperature. But the problem is, some kids are too lazy to do it and they just lie about their temperature.

Each student knows which of their classmates tells the truth and which one lies. The ones who tell the truth will simply say integer t_i — the value shown by their thermometer. The others act as follows. Each of them:

• chooses some non-empty subset of students R_i, who told the teacher the truth;
• picks a rounded down to the closest integer arithmetic mean of the values they stated: ;
• adds an arbitrary integer from  - x_i to x_i, inclusive: t_i = a + random( - x_i, x_i);
• tells the resulting value t_i to the teacher.

Numbers x_i are individual for each student and are known to everybody.

After all students said their t_i values, the teacher wondered: what minimum number of kids in the class could have told the truth?

The input contains several test cases. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 20) — the number of kids in the class. Next n lines contain pairs of integers t_i and x_i (1 ≤ t_i ≤ 10⁶; 0 ≤ x_i ≤ 10⁶) — the temperature the i-th student told and the maximum deviation from the mean if the student didn't tell the truth. The numbers on the lines are separated by a space.

For each test case, display the case number and a single positive integer — the minimum number of kids who could have told the truth.

3
1 0
2 2
3 1
4
10 5
20 5
15 1
25 6

Case 1: 2
Case 2: 2

In the first case, the first and third students told the truth and the second student told the teacher their mean temperature .

In the second case only the first and second students told the truth. The third student took the arithmetic mean of the first two and the arbitrary number he added was equal to 0, that is, . The fourth student took the temperature of the second student and the arbitrary number got equal to 5, that is .