Map Fragment Challenge

You are trapped in the arena of the dark magic temple. Initially, you are given a bag with a capacity of K. There are N challenges in sequence. For the i^th challenge, you are given an attribute a_i and a success probability of p_i%.

• If a_i \ge 0, then upon a successful challenge you obtain an additional bag with capacity a_i.
• If a_i = -1, then upon success you obtain a map fragment of size 1. Note: A map fragment must be stored in one of your bags. You do not need to fill the bag exactly, but you must be able to store all map fragments you obtain.

To be allowed to leave the arena, you must satisfy both of the following conditions after all challenges have been attempted:

1. You have succeeded in at least L challenges.
2. Your total bag capacity is at least equal to the total number of map fragments obtained.

More formally, if you define the net capacity after all N challenges as

[ \text{Net Capacity} = K + \sum_{i:, a_i \ge 0 \text{ and challenge } i \text{ succeeds}} a_i - \sum_{i:, a_i = -1 \text{ and challenge } i \text{ succeeds}}, ]

then you can leave if and only if Net Capacity \(\ge 0\) and the total number of successful challenges \(\ge L\).

Your task is to compute the probability that, after attempting all challenges, you will meet both conditions and be able to leave the arena. All challenges are independent.

inputFormat

The first line contains three integers N, K, and L (1 \le N \le 50, 1 \le K \le 100, 1 \le L \le N).

The second line contains N space-separated integers a₁, a₂, \dots, a_N. For each i, either a_i \ge 0 (indicating the capacity of a bag obtained on success) or a_i = -1 (indicating obtaining a map fragment of size 1).

The third line contains N space-separated integers p₁, p₂, \dots, p_N, where p_i (an integer between 0 and 100) represents the success probability (in percent) for the i^th challenge.

outputFormat

Output a single floating point number representing the probability that you will leave the arena, i.e. you have succeeded in at least L challenges and your total bag capacity is at least the number of map fragments obtained. The answer should be printed with at least 6 decimal places of precision.

sample

3 2 2
3 -1 -1
50 50 50

0.500000