← 返回题目列表

Codeforces · 739/E

E. Gosha 正在狩猎

中文机器翻译题面 查看原题

Gosha 正在狩猎。他的目标是捕捉尽可能多的神奇宝贝。 Gosha 有一个精灵球和 b 个超级球。有n只神奇宝贝。它们的编号为 1 到 n。 Gosha 知道,如果他向第 i 个神奇宝贝扔一个精灵球,他接住它的概率为 pi。如果他向第 i 个神奇宝贝扔一个超级球,他就会以 ui 的概率接住它。他最多可以向任何神奇宝贝投掷每种类型的一个球。

狩猎进行如下:首先,Gosha 选择不超过 1 只 Pokemon 来投掷精灵球,不超过 b 只 Pokemon 来投掷超级球。之后,他将选定的球扔向选定的神奇宝贝。如果他向某些神奇宝贝同时投掷超级球和精灵球,当且仅当他被这些球中的任何一个抓住时,他才会被抓住。一次投掷的结果不依赖于其他投掷。

Gosha 想知道如果他以最佳方式行动,他捕获的神奇宝贝的预期数量是多少。换句话说,他想知道最大可能捕获的神奇宝贝数量。

输入

第一行包含三个整数 n、a 和 b (2 ≤ n ≤ 2000, 0 ≤ a, b ≤ n) — 神奇宝贝数量、精灵球数量和超级球数量。

第二行包含 n 个实数值 p1, p2, ..., pn (0 ≤ pi ≤ 1),其中 pi 是 Gosha 向第 i 个神奇宝贝扔精灵球时捕获它的概率。

第三行包含 n 个实数值 u1, u2, ..., un (0 ≤ ui ≤ 1),其中 ui 是 Gosha 向第 i 个 Pokemon 投掷 Ultra Ball 时捕获该 Pokemon 的概率。

所有概率均以小数点分隔符后的三位数字给出。

输出

打印 Gosha 可以捕获的最大可能的神奇宝贝数量。如果绝对误差或相对误差不超过 10 - 4,则答案被认为是正确的。

示例

输入 #1

3 2 2
1.000 0.000 0.500
0.000 1.000 0.500

输出 #1

2.75

输入 #2

4 1 3
0.100 0.500 0.500 0.600
0.100 0.500 0.900 0.400

输出 #2

2.16

输入 #3

3 2 0
0.412 0.198 0.599
0.612 0.987 0.443

输出 #3

1.011