Air Strike#1276

Air Strike

1 second

64 megabytes

Hard

General Gee is the commander of a military base. He has just received alarming news from one of his spies: the enemy is preparing an air missile strike. The base contains two magnetic towers. When activated and given sufficient power, each of these towers creates a powerful horizontal magnetic disk. If any missile passes through this disk, it is deflected away from the base.

Although these towers seem to be an excellent air defense method, there is a problem: the area of the disk generated by a tower is proportional to the amount of energy it receives. The base has enough power plants to generate a certain amount of energy, which must be divided among these two towers. This means that the total area of the two disks generated by the towers should not exceed the total energy produced by the power plants. Fortunately, the spy was able to find out the exact target coordinates of the incoming missiles and reported them to General Gee. The General needs your help in distributing the energy between the two magnetic towers to minimize the number of missiles that will not be deflected and therefore will hit the base. You may assume the following:

The towers have different heights, so there are no issues with the magnetic disks interfering with each other.
A missile will be deflected if it passes through a tower's magnetic disk or even if it just touches its boundary.
A missile that lands exactly on the tower's location will be deflected, even if the tower receives no energy.
All incoming missiles will land simultaneously at the same instant, so there will not be time to redistribute energy between the towers during the strike.

Input

Input consists of several test cases. Each test case is given in $N + 2$ N+2 lines. The first line contains one integer ( $1 \leq N \leq 1000$ 1 \leq N \leq 1\,000), representing the number of missiles. The second line contains $5$ real numbers $X_{1}, Y_{1}, X_{2}, Y_{2}, T$ X_1, Y_1, X_2, Y_2, T: $(X_{1}, Y_{1})$ (X_1, Y_1) are the coordinates of the first tower, $(X_{2}, Y_{2})$ (X_2, Y_2) are the coordinates of the second tower, and $T$ is the total energy generated by the power plants (the total area of the two magnetic disks). Each of the following $N$ lines contains two real numbers indicating the landing coordinates of a missile.

The absolute value of all given real numbers does not exceed $100$ and may include a decimal point followed by up to $3$ digits. Any two consecutive numbers on the same line are separated by one or more whitespace characters. Zero or more blank lines may appear between test cases.

The last line of the input file consists of a single zero.

Output

For each test case, print the following line:

k. M

Where $k$ is the test case number (starting from $1$ ), and $M$ is the minimum number of missiles that will NOT be deflected for the best distribution of energy between the two towers. Use $π = 3.141$ \pi = 3.141.

Note: There is a blank space before $M$ .

Examples

Example 1