Description

The famous singer LAALA recently got hooked on a racing game. In the game, the driver must choose different speeds on different road segments to reach the finish in the shortest possible time. At the start, the car has initial fuel amount $f$, so the key is to balance speed and fuel consumption.

After some study, LAALA found that the game can be described by a simple mathematical model. The route from start to finish is simplified into a polyline, where each line segment represents an uphill or a downhill. If you drive on a road segment with slope $s$ ($s > 0$ means uphill, $s = 0$ means flat, $s < 0$ means downhill) at speed $v$ km/h, then the fuel consumption per kilometer is $\max(0, a v + b s)$, where $a$ and $b$ are built-in parameters of the game, representing the fuel consumption rate on flat ground and the effect of slope on fuel consumption, respectively (with $b$ always positive). It is assumed that accelerating and decelerating consume no fuel and are instantaneous, so you may adopt different speeds even within the same segment to reduce the total time.

Because LAALA has not performed well in previous games, the current car is still the initial one assigned by the system, so its speed cannot exceed vmax km/h. Given these parameters, LAALA wants to know the best result possible under limited initial fuel (no refueling on the way). As a fan of LAALA, can you help?

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case:

• The first line contains four floating-point numbers $a$, $b$, vmax, and $f$, where $a$, $b$, and vmax are as described above, and $f$ is the initial fuel amount (units consistent with the description above).
• The second line contains a positive integer $r$, the number of line segments.
• Each of the next $r$ lines contains two floating-point numbers $x_i$ and $y_i$, denoting the changes in the horizontal and vertical directions (in meters) of that segment in the standard Cartesian coordinate system.

Output Format

Output $T$ lines, corresponding to the $T$ test cases in order. For a test case, if the finish cannot be reached with the given initial fuel, output IMPOSSIBLE. Otherwise, output the minimum required time in hours.

3
10.0 1.0 150 0.0
1
100.0 -100.0
10.0 100.0 150 1.0
2
100 0
100 100
0.5 0.1 100 10
3
1000 0
100 10
100 -10

1.41421
IMPOSSIBLE
0.07212

Hint

Constraints:

For 100% of the testdata, $T \le 100$, $0.1 \le a \le 100$, $0.1 \le b \le 100$, $10 \le \text{vmax} \le 200$, $0 \le f \le 50$, $r \le 10000$, $1 \le x_i \le 1000$, $-1000 \le y_i \le 1000$, and if the problem has a solution, the answer does not exceed $24$.

Your output must have exactly 5 digits after the decimal point. Your output is considered correct if and only if it matches the standard answer exactly.

Translated by ChatGPT 5