{"problem":{"name":"C. Fly","description":{"content":"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 Ea","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1011C"},"statements":[{"statement_type":"Markdown","content":"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$.\n\nFlight 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.\n\nThe 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.\n\nFor 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.\n\nPlease 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.\n\nHelp 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.\n\n## Input\n\nThe first line contains a single integer $n$ ($2 \\le n \\le 1000$) — number of planets.\n\nThe second line contains the only integer $m$ ($1 \\le m \\le 1000$) — weight of the payload.\n\nThe 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.\n\nThe 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.\n\nIt is guaranteed, that if Natasha can make a flight, then it takes no more than $10^9$ tons of fuel.\n\n## Output\n\nIf 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$.\n\nIt is guaranteed, that if Natasha can make a flight, then it takes no more than $10^9$ tons of fuel.\n\nThe 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}$.\n\n[samples]\n\n## Note\n\nLet's consider the first example.\n\nInitially, the mass of a rocket with fuel is $22$ tons.\n\n*   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.\n*   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.\n*   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.\n*   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.\n\nIn the second case, the rocket will not be able even to take off from Earth.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Natasha 将乘坐火箭前往火星并返回地球。在前往火星的途中，她将登陆 $n -2$ 个中间行星。形式上：我们将所有行星编号为 $1$ 到 $n$。$1$ 是地球，$n$ 是火星。Natasha 将进行恰好 $n$ 次飞行：$1 \\to 2 \\to \\dots \\to n \\to 1$。\n\n从 $x$ 到 $y$ 的飞行包括两个阶段：从行星 $x$ 起飞和在行星 $y$ 着陆。因此，整个行程的顺序为：第 $1$ 个行星 $\\to$ 从第 $1$ 个行星起飞 $\\to$ 在第 $2$ 个行星着陆 $\\to$ 第 $2$ 个行星 $\\to$ 从第 $2$ 个行星起飞 $\\to$ $\\dots \\to$ 在第 $n$ 个行星着陆 $\\to$ 第 $n$ 个行星 $\\to$ 从第 $n$ 个行星起飞 $\\to$ 在第 $1$ 个行星着陆 $\\to$ 第 $1$ 个行星。\n\n火箭及其所有有效载荷（不含燃料）的质量为 $m$ 吨。然而，Natasha 不知道应该装载多少燃料。不幸的是，燃料只能在地球上装载，因此如果火箭在其他行星上耗尽燃料，Natasha 将无法回家。燃料用于从每个行星起飞和在每个行星着陆。已知 $1$ 吨燃料可以从第 $i$ 个行星起飞 $a_i$ 吨的火箭，或在第 $i$ 个行星着陆 $b_i$ 吨的火箭。\n\n例如，如果火箭重量为 $9$ 吨，燃料重量为 $3$ 吨，起飞系数为 $8$（即 $a_i = 8$），则将消耗 $1.5$ 吨燃料（因为 $1.5 \\times 8 = 9 + 3$）。起飞后燃料的新重量为 $1.5$ 吨。\n\n请注意，在起飞或着陆期间允许消耗非整数的燃料，初始燃料量也可以是非整数。\n\n请帮助 Natasha 计算需要装载到火箭中的最小燃料质量。请注意，火箭必须携带有效载荷和燃料本身，但不需要携带已经燃烧掉的燃料。假设火箭的起飞和着陆是瞬时的。\n\n第一行包含一个整数 $n$（$2 \\le n \\le 1000$）——行星数量。\n\n第二行包含一个整数 $m$（$1 \\le m \\le 1000$）——有效载荷质量。\n\n第三行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$（$1 \\le a_i \\le 1000$），其中 $a_i$ 表示一吨燃料可以从第 $i$ 个行星起飞的火箭吨数。\n\n第四行包含 $n$ 个整数 $b_1, b_2, \\dots, b_n$（$1 \\le b_i \\le 1000$），其中 $b_i$ 表示一吨燃料可以在第 $i$ 个行星着陆的火箭吨数。\n\n保证如果 Natasha 能完成飞行，则所需燃料不超过 $10^9$ 吨。\n\n如果 Natasha 能够通过 $(n -2)$ 个行星飞往火星并返回地球，请输出她应装载的最小燃料质量（单位：吨）；否则，输出 $-1$。\n\n保证如果 Natasha 能完成飞行，则所需燃料不超过 $10^9$ 吨。\n\n你的答案若满足绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。形式上，设你的答案为 $p$，标准答案为 $q$，当 $\\frac{|p - q|}{\\max(1, |q|)} \\le 10^{-6}$ 时，你的答案正确。\n\n考虑第一个例子：\n\n最初，火箭与燃料的总质量为 $22$ 吨。\n\n在第二种情况下，火箭甚至无法从地球起飞。\n\n## Input\n\n第一行包含一个整数 $n$（$2 \\le n \\le 1000$）——行星数量。\n\n第二行包含一个整数 $m$（$1 \\le m \\le 1000$）——有效载荷质量。\n\n第三行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$（$1 \\le a_i \\le 1000$），其中 $a_i$ 表示一吨燃料可以从第 $i$ 个行星起飞的火箭吨数。\n\n第四行包含 $n$ 个整数 $b_1, b_2, \\dots, b_n$（$1 \\le b_i \\le 1000$），其中 $b_i$ 表示一吨燃料可以在第 $i$ 个行星着陆的火箭吨数。保证如果 Natasha 能完成飞行，则所需燃料不超过 $10^9$ 吨。\n\n## Output\n\n如果 Natasha 能够通过 $(n -2)$ 个行星飞往火星并返回地球，请输出她应装载的最小燃料质量（单位：吨）；否则，输出 $-1$。保证如果 Natasha 能完成飞行，则所需燃料不超过 $10^9$ 吨。你的答案若满足绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。形式上，设你的答案为 $p$，标准答案为 $q$，当 $\\frac{|p - q|}{\\max(1, |q|)} \\le 10^{-6}$ 时，你的答案正确。\n\n[samples]\n\n## Note\n\n考虑第一个例子：\n\n最初，火箭与燃料的总质量为 $22$ 吨。从地球起飞时，一吨燃料可提升 $11$ 吨载荷，因此要提升 $22$ 吨需要燃烧 $2$ 吨燃料。剩余火箭与燃料总质量为 $20$ 吨。在火星着陆时，一吨燃料可降落 $5$ 吨载荷，因此降落 $20$ 吨需要燃烧 $4$ 吨燃料，剩余 $16$ 吨。从火星起飞时，一吨燃料可提升 $8$ 吨载荷，因此提升 $16$ 吨需要燃烧 $2$ 吨燃料，剩余 $14$ 吨。在地球着陆时，一吨燃料可降落 $7$ 吨载荷，因此降落 $14$ 吨需要燃烧 $2$ 吨燃料，最终剩余 $12$ 吨，即无燃料的火箭。\n\n在第二种情况下，火箭甚至无法从地球起飞。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of planets, numbered $ 1 $ to $ n $, where planet $ 1 $ is Earth and planet $ n $ is Mars.  \nLet $ m \\in \\mathbb{R}^+ $ be the mass of the rocket without fuel (payload).  \nLet $ a_i \\in \\mathbb{R}^+ $ be the take-off efficiency coefficient for planet $ i $: 1 ton of fuel can lift $ a_i $ tons of total mass.  \nLet $ b_i \\in \\mathbb{R}^+ $ be the landing efficiency coefficient for planet $ i $: 1 ton of fuel can land $ b_i $ tons of total mass.  \n\nThe rocket performs $ n $ flights: $ 1 \\to 2 \\to \\cdots \\to n \\to 1 $.  \nEach flight from planet $ i $ to planet $ j $ consists of:  \n- Take-off from $ i $, consuming fuel proportional to the total mass at $ i $,  \n- Landing on $ j $, consuming fuel proportional to the total mass during descent.  \n\nLet $ f_i $ be the fuel mass just before take-off from planet $ i $.  \nLet $ f_i' $ be the fuel mass just before landing on planet $ i $.  \n\nThe total mass during take-off from planet $ i $ is $ m + f_i $.  \nThe total mass during landing on planet $ i $ is $ m + f_i' $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 1000 $  \n2. $ 1 \\leq m \\leq 1000 $  \n3. $ 1 \\leq a_i, b_i \\leq 1000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. Fuel consumption must satisfy:  \n   - For take-off from planet $ i $: $ f_i - f_i' = \\frac{m + f_i}{a_i} $  \n   - For landing on planet $ j $: $ f_j' - f_{j} = \\frac{m + f_j'}{b_j} $ (with appropriate indexing)  \n\nThe journey is cyclic:  \n- Start at Earth (planet 1) with initial fuel $ F $.  \n- Sequence of operations:  \n  - Take-off from 1 → land on 2 → take-off from 2 → land on 3 → ... → take-off from n → land on 1.  \n\n**Objective**  \nFind the minimum initial fuel $ F = f_1 $ such that the rocket completes the full cycle $ 1 \\to 2 \\to \\cdots \\to n \\to 1 $, with non-negative fuel at all stages.  \n\nIf no such $ F $ exists (i.e., for some $ i $, $ a_i \\leq 1 $ or $ b_i \\leq 1 $, making take-off or landing impossible), output $ -1 $.  \n\nOtherwise, compute $ F $ via backward simulation:  \nLet $ M = m $ (payload mass).  \nStart from the end: after landing on Earth (planet 1), fuel is 0.  \nWork backwards through each landing and take-off to compute the required fuel before each phase.  \n\nFor $ i = n, n-1, \\dots, 1 $:  \n- Before landing on $ i $: fuel needed is $ f_i' = \\frac{M}{b_i - 1} $, if $ b_i > 1 $, else impossible.  \n- Then, before take-off from $ i $: fuel needed is $ f_i = \\frac{M + f_i'}{a_i - 1} $, if $ a_i > 1 $, else impossible.  \n- Update $ M = M + f_i $ (mass before take-off becomes new payload for previous leg).  \n\nFinal $ F = f_1 $.  \n\n**Formal Recurrence**  \nInitialize $ M = m $.  \nFor $ i $ from $ n $ down to $ 1 $:  \n1. If $ b_i \\leq 1 $, return $ -1 $.  \n   $ f_i' = \\frac{M}{b_i - 1} $  \n2. If $ a_i \\leq 1 $, return $ -1 $.  \n   $ f_i = \\frac{M + f_i'}{a_i - 1} $  \n3. $ M \\leftarrow M + f_i $  \n\nOutput $ f_1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1011C","tags":["binary search","greedy","math"],"sample_group":[["2\n12\n11 8\n7 5","10.0000000000"],["3\n1\n1 4 1\n2 5 3","\\-1"],["6\n2\n4 6 3 3 5 6\n2 6 3 6 5 3","85.4800000000"]],"created_at":"2026-03-03 11:00:39"}}