You're driving your car in the local hills and returning to your home
town. You'd like to get back as quickly as possible; however, you
notice that you don't have much fuel left. You know the most efficient
route to take. Some parts of this route go downhill, and some go
uphill. The different parts have different lengths and slopes. How
quickly can you reach home with the little fuel you have left?
We will assume a very simple model for the fuel consumption of your
car. Fuel consumption (per unit distance travelled) will increase
linearly with your driving speed v. However, there is an offset
which depends on the slope s of the hill. For example, when going
downhill along a particular road, you might be able to go at 10 km/h without expending any
fuel; on the other hand, if you were travelling that same road uphill, you
would expend fuel at the same rate as if you were driving 10 km/h faster along a flat
road. More specifically, the car's fuel consumption c in liters per
kilometer is given by
c =
max
(0,α v + β s),
(1)
where α is the standard fuel consumption rate on a flat road, v
is your speed in km/h, s is the slope of the road, and β is a positive
constant. Acceleration and deceleration do not cost fuel and can be
done instantaneously.
Note that your car has a maximum (safe) speed which cannot be
exceeded.
Input
On the first line a positive integer: the number of test cases, at
most 100. After that per test case:
One line with four floating point numbers α
(0.1 ≤ α ≤ 100), β (0.1 ≤ β ≤ 100),
vmax (10 ≤ vmax ≤ 200) and f (0 ≤ f ≤ 50): the standard (flat road) fuel consumption rate of your car, the
slope factor, the maximum speed of your car in km/h, and the amount of
fuel you have left in liters, respectively.
One line with an integer r (1 ≤ r ≤ 10 000): the number of
road segments.
r lines with two floating point numbers xi and yi
(1 ≤ xi ≤ 1 000, −1 000 ≤ y ≤ 1 000) each: the
horizontal distance and height change (both in meters) of the i-th road
segment. Each road segment has constant slope.
Output
Per test case:
One line with a floating point number: the fastest time in hours
in which you can reach town. It is guaranteed that if it is possible
to reach town at all, it will always be possible in less than 24
hours. If it is impossible to reach town, the line must contain
"IMPOSSIBLE" instead.
Your output should have a relative or absolute error of at most
10−6.