Hill Drive

Time limit1sMemory limit128 MB

Summary

Given fuel and a per-road speed-dependent consumption model with a speed cap, choose speeds per road segment to minimize total travel time under a total fuel budget.

Level: Hard8 of 10
Topics: Binary search, Greedy, Math
Solved: No attempts yet

Problem

Sanggeun has driven up a nearby mountain and now wants to get back home as quickly as possible. His car is low on fuel, so he has to drive as efficiently as he can.

Part of the way home is uphill and part is downhill. Every road segment has its own length and slope. Given how much fuel is left in the car, determine the shortest possible time to get home.

The car's fuel usage is modeled simply. The fuel consumption $c$ (liters per km) grows in proportion to the speed $v$ and is offset by the slope $s$ of the road:

$c = \max(0,\ \alpha v + \beta s)$

Here $\alpha$ is the flat-ground consumption factor, $v$ is the speed in km/h, $s$ is the slope of the road, and $\beta$ is a positive constant. For intuition, suppose a hill can be descended at $10$ km/h while burning no fuel; driving up that same hill then uses as much fuel as driving $10$ km/h faster on flat ground. Accelerating and decelerating use no fuel and happen instantly. The car also has a top speed $v_{max}$ that it can never exceed.

Distances are given in meters. For a road segment with horizontal length $x$ and height change $y$ , the actual distance driven is $\sqrt{x^2 + y^2}$ meters and its slope is $s = y / x$ . Speeds are in km/h and the travel time is measured in hours.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100$ ). Each test case is given as follows.

The first line of a test case contains four real numbers $\alpha$ ( $0.5 \le \alpha \le 100$ ), $\beta$ ( $0.1 \le \beta \le 100$ ), $v_{max}$ ( $10 \le v_{max} \le 200$ ), and $f$ ( $0 \le f \le 50$ ), where $v_{max}$ is the car's top speed in km/h and $f$ is the fuel left in liters.

The next line contains the number of roads $r$ ( $1 \le r \le 10000$ ).

Each of the next $r$ lines contains two real numbers $x_i$ and $y_i$ ( $1 \le x_i \le 1000$ , $-1000 \le y_i \le 1000$ ): the horizontal length and the height change of the $i$ -th road, both in meters. Each road has a constant slope.

Output

For each test case, print on its own line the minimum time in hours needed to get home, rounded to exactly 6 digits after the decimal point (for example, printf("%.6f")). If it is impossible to get home with the available fuel, print IMPOSSIBLE instead. When getting home is possible, the required time is always less than 24 hours. The test data is chosen so that the exact answer is never close to a rounding boundary.

Examples4

Example 1

Input

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

Expected output

1.414214
IMPOSSIBLE
0.072120

Example 2
Input
```
1
2.0 1.0 120 30
1
800 0
```
Expected output
```
0.042667
```

Example 3

Input

1
5.0 20.0 100 2.0
1
300 250

Expected output

IMPOSSIBLE

Example 4

Input

2
1.5 2.0 100 18
2
900 10
200 -30
6.0 0.5 160 40
2
1000 0
150 120

Expected output

0.101026
0.213573