Fly
Contest: Codeforces Round 499 (Div. 1)
Difficulty rating: 1500
Tags: binary search, math

Natasha is going to fly on a rocket to Mars and return to Earth. Also, on the way to Mars, she will land on $$$n - 2$$$ intermediate planets. Formally: we number all the planets from $$$1$$$ to $$$n$$$. $$$1$$$ is Earth, $$$n$$$ is Mars. Natasha will make exactly $$$n$$$ flights: $$$1 \to 2 \to \ldots n \to 1$$$.

Flight from $$$x$$$ to $$$y$$$ consists of two phases: take-off from planet $$$x$$$ and landing to planet $$$y$$$. This way, the overall itinerary of the trip will be: the $$$1$$$-st planet $$$\to$$$ take-off from the $$$1$$$-st planet $$$\to$$$ landing to the $$$2$$$-nd planet $$$\to$$$ $$$2$$$-nd planet $$$\to$$$ take-off from the $$$2$$$-nd planet $$$\to$$$ $$$\ldots$$$ $$$\to$$$ landing to the $$$n$$$-th planet $$$\to$$$ the $$$n$$$-th planet $$$\to$$$ take-off from the $$$n$$$-th planet $$$\to$$$ landing to the $$$1$$$-st planet $$$\to$$$ the $$$1$$$-st planet.

The mass of the rocket together with all the useful cargo (but without fuel) is $$$m$$$ tons. However, Natasha does not know how much fuel to load into the rocket. Unfortunately, fuel can only be loaded on Earth, so if the rocket runs out of fuel on some other planet, Natasha will not be able to return home. Fuel is needed to take-off from each planet and to land to each planet. It is known that $$$1$$$ ton of fuel can lift off $$$a_i$$$ tons of rocket from the $$$i$$$-th planet or to land $$$b_i$$$ tons of rocket onto the $$$i$$$-th planet.

For example, if the weight of rocket is $$$9$$$ tons, weight of fuel is $$$3$$$ tons and take-off coefficient is $$$8$$$ ($$$a_i = 8$$$), then $$$1.5$$$ tons of fuel will be burnt (since $$$1.5 \cdot 8 = 9 + 3$$$). The new weight of fuel after take-off will be $$$1.5$$$ tons.

Please note, that it is allowed to burn non-integral amount of fuel during take-off or landing, and the amount of initial fuel can be non-integral as well.

Help Natasha to calculate the minimum mass of fuel to load into the rocket. Note, that the rocket must spend fuel to carry both useful cargo and the fuel itself. However, it doesn't need to carry the fuel which has already been burnt. Assume, that the rocket takes off and lands instantly.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 1000$$$) — number of planets.

The second line contains the only integer $$$m$$$ ($$$1 \le m \le 1000$$$) — weight of the payload.

The third line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$), where $$$a_i$$$ is the number of tons, which can be lifted off by one ton of fuel.

The fourth line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 1000$$$), where $$$b_i$$$ is the number of tons, which can be landed by one ton of fuel.

It is guaranteed, that if Natasha can make a flight, then it takes no more than $$$10^9$$$ tons of fuel.

Output format:
If Natasha can fly to Mars through $$$(n - 2)$$$ planets and return to Earth, print the minimum mass of fuel (in tons) that Natasha should take. Otherwise, print a single number $$$-1$$$.

It is guaranteed, that if Natasha can make a flight, then it takes no more than $$$10^9$$$ tons of fuel.

The answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$. Formally, let your answer be $$$p$$$, and the jury's answer be $$$q$$$. Your answer is considered correct if $$$\frac{|p - q|}{\max{(1, |q|)}} \le 10^{-6}$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Let's consider the first example.

Initially, the mass of a rocket with fuel is $$$22$$$ tons.

- At take-off from Earth one ton of fuel can lift off $$$11$$$ tons of cargo, so to lift off $$$22$$$ tons you need to burn $$$2$$$ tons of fuel. Remaining weight of the rocket with fuel is $$$20$$$ tons.
- During landing on Mars, one ton of fuel can land $$$5$$$ tons of cargo, so for landing $$$20$$$ tons you will need to burn $$$4$$$ tons of fuel. There will be $$$16$$$ tons of the rocket with fuel remaining.
- While taking off from Mars, one ton of fuel can raise $$$8$$$ tons of cargo, so to lift off $$$16$$$ tons you will need to burn $$$2$$$ tons of fuel. There will be $$$14$$$ tons of rocket with fuel after that.
- During landing on Earth, one ton of fuel can land $$$7$$$ tons of cargo, so for landing $$$14$$$ tons you will need to burn $$$2$$$ tons of fuel. Remaining weight is $$$12$$$ tons, that is, a rocket without any fuel.

In the second case, the rocket will not be able even to take off from Earth.

Example input:
2
12
11 8
7 5

Example output:
10.0000000000

Example input:
3
1
1 4 1
2 5 3

Example output:
-1

Editorial:
First, we learn how to determine if a rocket can fly the entire route. Consider an element from an array $$$a[]$$$ or $$$b[]$$$. We denote it by $$$t$$$. If $$$t=1$$$ (that is, one ton of fuel can carry only one ton (cargo + fuel)), then fuel can only take it to ourselves, and we need to take a rocket and a useful cargo (the mass of which is positive). That is, if $$$t=1$$$ at least for one $$$t$$$, it is necessary to deduce $$$-1$$$, otherwise, do the following calculations.
It is clear that arrays $$$a[]$$$ and $$$b[]$$$ will be processed by the computer of the rocket in that order: $$$a_1,b_2,a_2,b_3,a_3,b_4,a_4,\ldots,b_{n-1},a_{n-1},b_n,a_n,b_1$$$. We will process this sequence from the end. Let at the current iteration the mass of the payload (including fuel that will not be used at this iteration) is $$$s$$$ tons, the current element from the array $$$a[]$$$ or $$$b[]$$$ is $$$t$$$, the mass of fuel that will be used at this iteration (it must be found), is $$$x$$$. We assign before the iterations $$$s=m$$$. We form the equation:
total mass = mass that all fuel can transport
$$$s+x=tx$$$
$$$x=\dfrac s{t-1}$$$
By this formula, you can find fuel in this iteration. For the next iteration to the payload weight, you need to add mass of fuel (since this fuel needs to be brought to this iteration), that is, perform the assignment $$$s=s+x$$$. In the end, it is necessary to deduce $$$s-m$$$.
Complexity: $$$O(n)$$$.
Bonus. In fact, it does not matter in which order to process arrays $$$a[]$$$ and $$$b[]$$$ (from the beginning, from the end or in general mixed): the answer from this will not change. Try to prove it by yourself.