Kiddie Pool

A kiddie pool is a big container you fill with water so that small children can play in it.

You have $N$ different water sources. Source $i$ produces water at a rate of $R_i$ liters per second and at a temperature of $C_i$ degrees. All sources start off. Each source can be switched on only once and switched off only once, and switching takes no time. Several sources can be on at the same time.

The pool holds any amount of water, but you want to fill it to a volume of exactly $V$ liters at a temperature of exactly $X$ degrees, as quickly as possible. If you turn the sources on and off optimally, what is the minimum number of seconds it takes? You do not have to use every source.

In this problem, combining water of volume $V_0$ and temperature $X_0$ with water of volume $V_1$ and temperature $X_1$ instantaneously produces water of volume $V_0 + V_1$ and temperature $(V_0 X_0 + V_1 X_1) / (V_0 + V_1)$. For example, combining 5 liters at 10 degrees with 10 liters at 40 degrees gives 15 liters at 30 degrees. Assume water neither heats nor cools over time except by being combined with other water.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains three space separated numbers $N$, $V$, and $X$. $N$ is an integer and $V$ and $X$ are real numbers. The next $N$ lines each contain the flow rate $R_i$ and the temperature $C_i$ of source $i$, separated by a space. Volume is in liters, flow rate is in liters per second, and temperature is in degrees Celsius.

Every real number is given with exactly four decimal places.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• $0.0001 \le V \le 10000.0$
• $0.1 \le X \le 99.9$
• $0.0001 \le R_i \le 1000.0$
• $0.1 \le C_i \le 99.9$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of seconds needed to fill the pool to the target volume at the target temperature. If the given input makes that impossible, print IMPOSSIBLE in place of $y$.

Print $y$ with exactly nine digits after the decimal point. Round at the tenth digit, and round up when the value is exactly halfway. An answer of 50 seconds is printed as 50.000000000.

In Case #1 of the first sample, the only source is already at the target temperature. The best plan is to switch it on immediately and let it run until the pool holds 10 liters. It delivers 0.2 liters per second, so this takes 50 seconds.

In Case #2, one optimal plan is to run the first source for 207221.843687375 seconds and also switch the second source on about 0.092778156 seconds before the end.

In Case #3, both sources are colder than the target temperature, so the target cannot be reached.