Gosha is hunting
Contest: Codeforces Round 381 (Div. 1)
Difficulty rating: 3000
Tags: brute force, data structures, dp, flows, math, probabilities, sortings

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 pi. If he throws an Ultra Ball at the i-th Pokemon he catches it with probability ui. 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 format:
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 p1, p2, ..., pn (0 ≤ pi ≤ 1), where pi is the probability of catching the i-th Pokemon if Gosha throws a Poke Ball to it.

The third line contains n real values u1, u2, ..., un (0 ≤ ui ≤ 1), where ui 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 format:
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.

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

Example input:
3 2 2
1.000 0.000 0.500
0.000 1.000 0.500

Example output:
2.75

Example input:
4 1 3
0.100 0.500 0.500 0.600
0.100 0.500 0.900 0.400

Example output:
2.16

Editorial:
Let's divide Pokemons into 4 types: 0, A, B and AB depending on Balls that we throw to them. Let's sort them by u in descending order. Let's iterate over last Pokemon in which we throw Ultra Ball (his type is B or AB). Let i be the index of this Pokemon. It is not hard to prove that there are no Pokemons to the left of i that have type 0 and all Pokemons to the right of i have type 0 or A. Let's sort all Pokemons to the left of i by (1 - p) * u in descending order. Let's iterate last Pokemon of type AB. Let j be his index. We can prove that to the left of j every Pokemon has type AB or B (Let's call this group of Pokemons X). Between j and i every Pokemon has type A or B (will call them Y). To the right of i only 0 and A (will call them Z). We know that we throw an Ultra Ball to every Pokemon in X. So let's add to our answer sum of u of all Pokemons in X. Number of Pokemons in Y of type B equals to the difference between b (number of Ultra Balls) and size of X. Therefore we know number of Pokemons in Y of type A and we know how many Poke Balls are left for X and Z summarily. Not hard to prove that in group Y we should throw Poke Balls to Pokemons with greatest u - p. Now we have to understand in which Pokemons in X and Z we should throw Poke Balls. If we throw Poke Ball to Pokemon from X, it adds to the answer p * (1 - u), from Z - adds p. So we should throw Poke Balls to Pokemons with greatest values. When we iterate over j, each iteration one Pokemon moves from Y to X. We can keep structure that can add and delete one element, find minimum and keep sum of all elements in the structure. For example, treap or map (in c++). Let's keep 2 such structures: for calculating answer for Y and for calculating answer for throwing Poke Balls to Pokemons in X and Z. The complexity - O(n2·logn).