Наташа собирается на ракете полететь на Марс и вернуться на Землю. Также по пути на Марс она приземлится ещё на \(n - 2\) планетах. Формально: пронумеруем все планеты от \(1\) до \(n\). \(1\) — Земля, \(n\) — Марс. Наташа собирается сделать ровно \(n\) полётов: \(1 \to 2 \to \ldots n \to 1\).
Перелёт с планеты \(x\) на планету \(y\) состоит из двух фаз: взлёт с планеты \(x\) и приземление на планету \(y\). Таким образом, полный маршрут поездки выглядит следующим образом: \(1\)-я планета \(\to\) взлёт с \(1\)-й планеты \(\to\) торможение ко \(2\)-й планете \(\to\) \(2\)-я планета \(\to\) взлёт со \(2\)-й планеты \(\to\) \(\ldots\) \(\to\) торможение к \(n\)-й планете \(\to\) \(n\)-я планета \(\to\) взлёт с \(n\)-й планеты \(\to\) торможение к \(1\)-й планете \(\to\) \(1\)-я планета.
Масса ракеты вместе с полезным грузом (но без топлива) равна \(m\) тоннам. Но Наташа не знает, сколько топлива нужно загрузить в ракету. К сожалению, топливо можно загрузить только на Земле, так что, если на какой-то другой планете топливо закончится, то Наташа не сможет вернуться домой. Топливо нужно для взлёта с каждой планеты и для торможения перед каждой планетой. Известно, что \(1\) тонна топлива может поднять с \(i\)-й планеты \(a_i\) тонн груза или затормозить перед \(i\)-й планетой \(b_i\) тонн груза.
Например, если масса ракеты составляет \(9\) тонн, масса топлива \(3\) тонны, а коэффициент при взлёте равен \(8\) (\(a_i = 8\)), то при взлёте сгорит \(1.5\) тоны топлива (так как \(1.5 \cdot 8 = 9 + 3\)). Новая масса топлива после взлёта будет равна \(1.5\) тоннам.
Обратите внимание, что можно использовать нецелый объём топлива при взлёте или посадке. Также, изначальное количество топлива может быть тоже нецелым.
Помогите Наташе посчитать, какую минимальную массу топлива нужно загрузить в ракету. Учтите, что, с одной стороны, ракета должна везти с помощью топлива не только полезный груз, но и само топливо, а, с другой стороны, топливо, которое сгорело раньше, везти не нужно. Считайте, что ракета мгновенно тормозит и мгновенно разгоняется.
Выходные данные
Если Наташа сможет долететь до Марса через \((n - 2)\) планеты и вернуться на Землю, выведите минимальную массу топлива (в тоннах), которое Наташа должна взять. В противном случае выведите в одно число \(-1\).
Гарантируется, что если Наташа может совершить полёт, то для этого ей понадобится не более \(10^9\) тонн топлива.
Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает \(10^{-6}\). Формально, пусть ваш ответ равен \(p\), а ответ жюри равен \(q\). Ваш ответ будет зачтен, если \(\frac{|p - q|}{\max{(1, |q|)}} \le 10^{-6}\).
Примечание
Рассмотрим первый пример.
Сначала масса ракеты с топливом — \(22\) тонны.
- При взлёте с Земли одна тонна топлива может поднять \(11\) тонн груза, поэтому для подъёма \(22\) тонн понадобится потратить \(2\) тонны топлива. Останется \(20\) тонн ракеты с топливом.
- При посадке на Марс одна тонна топлива может затормозить \(5\) тонн груза, поэтому для торможения \(20\) тонн понадобится потратить \(4\) тонны топлива. Останется \(16\) тонн ракеты с топливом.
- При взлёте с Марса одна тонна топлива может поднять \(8\) тонн груза, поэтому для подъёма \(16\) тонн понадобится потратить \(2\) тонны топлива. Останется \(14\) тонн ракеты с топливом.
- При посадке на Землю одна тонна топлива может затормозить \(7\) тонн груза, поэтому для торможения \(14\) тонн понадобится потратить \(2\) тонны топлива. Останется \(12\) тонн, то есть только ракета.
Во втором примере ракета даже не сможет взлететь с Земли.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
12
11 8
7 5
|
10.0000000000
|
|
2
|
3
1
1 4 1
2 5 3
|
-1
|
|
3
|
6
2
4 6 3 3 5 6
2 6 3 6 5 3
|
85.4800000000
|