Водіння в горах#2452

Водіння в горах

1 секунда

64 мегабайти

Середня

Ви їдете на своєму автомобілі по місцевих пагорбах і повертаєтесь до рідного міста. Ви хочете дістатися якомога швидше; однак помічаєте, що у вас майже не залишилося пального. Ви знаєте найефективніший маршрут. Деякі ділянки цього маршруту проходять під гору, а деякі — вгору. Довжина та ухил цих ділянок різні. Наскільки швидко ви зможете доїхати додому з тією невеликою кількістю пального, що у вас залишилась?

Ми будемо розглядати дуже просту модель витрати пального вашого автомобіля. Витрата пального (на одиницю пройденої відстані) лінійно зростає зі швидкістю руху $v$ . Однак, є й зсув, який залежить від ухилу $s$ дороги. Наприклад, рухаючись під гору певною дорогою, ви можете їхати зі швидкістю $10$ км/год без витрати пального; з іншого боку, якщо їхати цією ж дорогою вгору, ви витрачатимете пальне так, як ніби їхали на $10$ км/год швидше по рівній дорозі. Точніше, витрата пального $c$ в літрах на кілометр визначається за формулою

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

де $α$ — стандартна витрата пального на рівній дорозі, $v$ — ваша швидкість у км/год, $s$ — ухил дороги, а $β$ — додатна константа. Прискорення та гальмування не витрачають пального й можуть виконуватись миттєво.

Зверніть увагу, що у вашого автомобіля є максимальна (безпечна) швидкість, яку не можна перевищувати.

Вхідні дані

У першому рядку міститься одне ціле додатне число: кількість тестових випадків, не більше $100$ . Далі для кожного тесту:

Один рядок з чотирма числами з плаваючою крапкою: $α$ ( $0.1 \leq α \leq 100$ 0.1 \leq \alpha \leq 100), $β$ ( $0.1 \leq β \leq 100$ 0.1 \leq \beta \leq 100), $v_{max}$ v_\text{max} ( $10 \leq v_{max} \leq 200$ 10 \leq v_\text{max} \leq 200) і $f$ ( $0 \leq f \leq 50$ 0 \leq f \leq 50): стандартна витрата пального (на рівній дорозі), коефіцієнт ухилу, максимальна швидкість автомобіля у км/год і кількість пального, що залишилась, відповідно.
Один рядок з цілим числом $r$ ( $1 \leq r \leq 10000$ 1 \leq r \leq 10\ 000): кількість сегментів дороги.
$r$ рядків, у кожному з яких два числа з плаваючою крапкою $x_{i}$ x_i та $y_{i}$ y_i ( $1 \leq x_{i} \leq 1000$ 1 \leq x_i \leq 1\ 000, $- 1000 \leq y_{i} \leq 1000$ -1\ 000 \leq y_i \leq 1\ 000): горизонтальна відстань і зміна висоти (обидві у метрах) для $i$ -го сегмента дороги. Кожен сегмент має постійний ухил.

Вихідні дані

Для кожного тестового випадку:

Один рядок з числом з плаваючою крапкою: найшвидший час у годинах, за який ви можете дістатися міста. Якщо це неможливо, рядок повинен містити IMPOSSIBLE.

Ваша відповідь повинна мати відносну або абсолютну похибку не більше, ніж $1 0^{- 6}$ 10^{-6}.

Приклади

Приклад 1