{"raw_statement":[{"iden":"statement","content":"Gosha is hunting. His goal is to catch as many Pokemons as possible. Gosha has _a_ Poke Balls and _b_ Ultra Balls. There are _n_ Pokemons. They are numbered 1 through _n_. Gosha knows that if he throws a Poke Ball at the _i_\\-th Pokemon he catches it with probability _p__i_. If he throws an Ultra Ball at the _i_\\-th Pokemon he catches it with probability _u__i_. He can throw at most one Ball of each type at any Pokemon.\n\nThe hunting proceeds as follows: at first, Gosha chooses no more than _a_ Pokemons at which he will throw Poke Balls and no more than _b_ Pokemons at which he will throw Ultra Balls. After that, he throws the chosen Balls at the chosen Pokemons. If he throws both Ultra Ball and Poke Ball at some Pokemon, he is caught if and only if he is caught by any of these Balls. The outcome of a throw doesn't depend on the other throws.\n\nGosha would like to know what is the expected number of the Pokemons he catches if he acts in an optimal way. In other words, he would like to know the maximum possible expected number of Pokemons can catch."},{"iden":"input","content":"The first line contains three integers _n_, _a_ and _b_ (2 ≤ _n_ ≤ 2000, 0 ≤ _a_, _b_ ≤ _n_) — the number of Pokemons, the number of Poke Balls and the number of Ultra Balls.\n\nThe second line contains _n_ real values _p_1, _p_2, ..., _p__n_ (0 ≤ _p__i_ ≤ 1), where _p__i_ is the probability of catching the _i_\\-th Pokemon if Gosha throws a Poke Ball to it.\n\nThe third line contains _n_ real values _u_1, _u_2, ..., _u__n_ (0 ≤ _u__i_ ≤ 1), where _u__i_ is the probability of catching the _i_\\-th Pokemon if Gosha throws an Ultra Ball to it.\n\nAll the probabilities are given with exactly three digits after the decimal separator."},{"iden":"output","content":"Print the maximum possible expected number of Pokemons Gosha can catch. The answer is considered correct if it's absolute or relative error doesn't exceed 10 - 4."},{"iden":"examples","content":"Input\n\n3 2 2\n1.000 0.000 0.500\n0.000 1.000 0.500\n\nOutput\n\n2.75\n\nInput\n\n4 1 3\n0.100 0.500 0.500 0.600\n0.100 0.500 0.900 0.400\n\nOutput\n\n2.16\n\nInput\n\n3 2 0\n0.412 0.198 0.599\n0.612 0.987 0.443\n\nOutput\n\n1.011"}],"translated_statement":[{"iden":"statement","content":"Gosha 正在狩猎。他的目标是捕捉尽可能多的宝可梦。Gosha 拥有 #cf_span[a] 个精灵球和 #cf_span[b] 个超级球。共有 #cf_span[n] 个宝可梦，编号为 #cf_span[1] 到 #cf_span[n]。Gosha 知道，如果他向第 #cf_span[i] 个宝可梦投掷一个精灵球，则捕捉它的概率为 #cf_span[pi]；如果投掷一个超级球，则捕捉它的概率为 #cf_span[ui]。对于任意一个宝可梦，他最多只能投掷每个类型的球一次。\n\n狩猎过程如下：首先，Gosha 选择至多 #cf_span[a] 个宝可梦投掷精灵球，以及至多 #cf_span[b] 个宝可梦投掷超级球。之后，他向选定的宝可梦投掷所选的球。如果他对某个宝可梦同时投掷了超级球和精灵球，则只要其中任意一个球捕捉成功，该宝可梦即被捕捉。每次投掷的结果与其他投掷无关。\n\nGosha 希望知道，若他采取最优策略，他能捕捉到的宝可梦的期望数量是多少。换句话说，他想知道能捕捉到的宝可梦的最大可能期望数量。\n\n第一行包含三个整数 #cf_span[n], #cf_span[a] 和 #cf_span[b]（#cf_span[2 ≤ n ≤ 2000]，#cf_span[0 ≤ a, b ≤ n]）——宝可梦的数量、精灵球的数量和超级球的数量。\n\n第二行包含 #cf_span[n] 个实数 #cf_span[p1, p2, ..., pn]（#cf_span[0 ≤ pi ≤ 1]），其中 #cf_span[pi] 表示当 Gosha 向第 #cf_span[i] 个宝可梦投掷精灵球时捕捉它的概率。\n\n第三行包含 #cf_span[n] 个实数 #cf_span[u1, u2, ..., un]（#cf_span[0 ≤ ui ≤ 1]），其中 #cf_span[ui] 表示当 Gosha 向第 #cf_span[i] 个宝可梦投掷超级球时捕捉它的概率。\n\n所有概率均精确到小数点后三位。\n\n请输出 Gosha 能捕捉到的宝可梦的最大可能期望数量。若答案的绝对误差或相对误差不超过 #cf_span[10 - 4]，则视为正确。"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n], #cf_span[a] 和 #cf_span[b]（#cf_span[2 ≤ n ≤ 2000]，#cf_span[0 ≤ a, b ≤ n]）——宝可梦的数量、精灵球的数量和超级球的数量。第二行包含 #cf_span[n] 个实数 #cf_span[p1, p2, ..., pn]（#cf_span[0 ≤ pi ≤ 1]），其中 #cf_span[pi] 表示当 Gosha 向第 #cf_span[i] 个宝可梦投掷精灵球时捕捉它的概率。第三行包含 #cf_span[n] 个实数 #cf_span[u1, u2, ..., un]（#cf_span[0 ≤ ui ≤ 1]），其中 #cf_span[ui] 表示当 Gosha 向第 #cf_span[i] 个宝可梦投掷超级球时捕捉它的概率。所有概率均精确到小数点后三位。"},{"iden":"output","content":"请输出 Gosha 能捕捉到的宝可梦的最大可能期望数量。若答案的绝对误差或相对误差不超过 #cf_span[10 - 4]，则视为正确。"},{"iden":"examples","content":"输入\n3 2 2\n1.000 0.000 0.500\n0.000 1.000 0.500\n输出\n2.75\n\n输入\n4 1 3\n0.100 0.500 0.500 0.600\n0.100 0.500 0.900 0.400\n输出\n2.16\n\n输入\n3 2 0\n0.412 0.198 0.599\n0.612 0.987 0.443\n输出\n1.011"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, a, b \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 2000 $, $ 0 \\leq a, b \\leq n $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ and $ U = (u_1, u_2, \\dots, u_n) $ be sequences of catch probabilities, where $ p_i, u_i \\in [0,1] $ for all $ i \\in \\{1, \\dots, n\\} $.  \n\nLet $ x_i \\in \\{0,1\\} $ indicate whether a Poke Ball is thrown at Pokemon $ i $, and $ y_i \\in \\{0,1\\} $ indicate whether an Ultra Ball is thrown at Pokemon $ i $.  \n\n**Constraints**  \n1. $ \\sum_{i=1}^n x_i \\leq a $  \n2. $ \\sum_{i=1}^n y_i \\leq b $  \n3. $ x_i, y_i \\in \\{0,1\\} $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nMaximize the expected number of caught Pokemons:  \n$$\n\\max \\sum_{i=1}^n \\left(1 - (1 - p_i)^{x_i} (1 - u_i)^{y_i} \\right)\n$$","simple_statement":null,"has_page_source":false}