Codeforces Round 381 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

data structures

dp

flows

math

probabilities

sortings

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Gosha is hunting

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGosha 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.

The 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.

Gosha 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.

Input

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.

The 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.

The 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.

All the probabilities are given with exactly three digits after the decimal separator.

Output

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}.

Examples

Input

3 2 2

1.000 0.000 0.500

0.000 1.000 0.500

Output

2.75

Input

4 1 3

0.100 0.500 0.500 0.600

0.100 0.500 0.900 0.400

Output

2.16

Input

3 2 0

0.412 0.198 0.599

0.612 0.987 0.443

Output

1.011

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/06/2024 16:37:10 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|