题目描述

A kiddie pool is a big container in which you can put water, so that small children can play in it.

You have access to $\mathbf{N}$ different sources of water. The $i^{\text {th }}$ source of water produces water at rate $\mathbf{R}_{i}$ and at temperature $\mathbf{C}_{i}$. Initially, all of the water sources are off. Each source of water can be switched on only once, and switched off only once; the act of switching a source on or off takes no additional time. Multiple sources can be on at the same time.

Your pool can hold an infinite amount of water, but you want to fill the pool to a volume of exactly $\mathbf{V}$ with a temperature of exactly $\mathbf{X}$, as quickly as possible. If you turn sources on and off optimally (not every source necessarily has to be used), what's the minimum number of seconds it will take you to do this?

For the purposes of this problem, combining water that has volume $\mathbf{V}_{0}$ and temperature $\mathbf{X}_{0}$ with water that has volume $\mathbf{V}_{1}$ and temperature $\mathbf{X}_{1}$ will instantaneously create water with volume $\mathbf{V}_{0}+\mathbf{V}_{1}$ and temperature $\left(\mathbf{V}_{0} \mathbf{X}_{0}+\mathbf{V}_{1} \mathbf{X}_{1}\right) /\left(\mathbf{V}_{0}+\mathbf{V}_{1}\right)$. For example, combining $5 \mathrm{~L}$ of water at 10 degrees with $10 \mathrm{~L}$ of water at 40 degrees will result in $15 \mathrm{~L}$ of water at 30 degrees. You should also assume that water does not heat or cool over time except as a result of being combined with other water.

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. The first line of each test case contains three space-separated numbers: an integer $\mathbf{N}$, and real numbers $\mathbf{V}$ and $\mathbf{X}$ as described above.

The next $\mathbf{N}$ lines each contain two space-separated real numbers, $\mathbf{R}_{i}$ and $\mathbf{C}_{i}$, the rate of flow and temperature of the $i^{\text {th }}$ water source respectively. The volume is expressed in liters, rates of flow are expressed in liters per second, and temperatures are expressed in degrees Celsius.

All real numbers will be exactly specified to four decimal places.

输出格式

For each test case, output one line containing "Case #x: y", where $\mathrm{x}$ is the test case number (starting from 1) and $\mathrm{y}$ is the minimum number of seconds it takes to fill the kiddie pool to the right volume and temperature. If it is impossible to do so given the inputs, $\mathrm{y}$ should be the string IMPOSSIBLE.

$\mathrm{y}$ will be considered correct if it is within an absolute or relative error of $10^{-6}$ of the correct answer.

6
1 10.0000 50.0000
0.2000 50.0000
2 30.0000 65.4321
0.0001 50.0000
100.0000 99.9000
2 5.0000 99.9000
30.0000 99.8999
20.0000 99.7000
2 0.0001 77.2831
0.0001 97.3911
0.0001 57.1751
2 100.0000 75.6127
70.0263 75.6127
27.0364 27.7990
4 5000.0000 75.0000
10.0000 30.0000
20.0000 50.0000
300.0000 95.0000
40.0000 2.0000

Case #1: 50.0000000
Case #2: 207221.843687375
Case #3: IMPOSSIBLE
Case #4: 0.500000000
Case #5: 1.428034895
Case #6: 18.975332068

提示

Sample Explanation

Note that Case #6 is not within the limits for the Small dataset.

In Case #1, the one available source happens to be the exact temperature we need. The optimal strategy is to immediately turn it on and let it run until we have $10$ L. Since $0.2$ L will come out every second, this takes $50$ seconds.

In Case #2, one optimal strategy is to turn on the first source and let it run for $207221.843687375$ seconds, and then, about $0.092778156$ seconds before the end, also turn on the second source.

In Case #3, both available water sources are cooler than the target temperature, so there is no way to reach it.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• $0.1 \leq \mathbf{X} \leq 99.9$.
• $0.1 \leq \mathbf{C}_{i} \leq 99.9$.

Small dataset(7 Pts)

• Time limit: 240 5 seconds.
• $1 \leq \mathbf{N} \leq 2$.
• $0.0001 \leq \mathbf{V} \leq 100.0$.
• $0.0001 \leq \mathbf{R}_{i} \leq 100.0$.

Large dataset(18 Pts)

• Time limit: 480 10 seconds.
• $1 \leq \mathbf{N} \leq 100$.
• $0.0001 \leq \mathbf{V} \leq 10000.0$.
• $0.0001 \leq \mathbf{R}_{i} \leq 10000.0$.