Blue Mary, the queen of Protoss, is planning a war against Zerg. Before the war she plans to make her base as safe as possible. Now there are N (1<= N <= 60) nexuses available in the region controlled by Protoss, numbered 1, 2 ... N. (Those who don't know what nexus is, please visit Blizzard Entertainment.) All the mineral and vespene gas stored in nexus i can be transported directly to nexus S_i.(i and S_i won't be the same.) Blue Mary's base is nexus 1, So all the mineral and vespene gas can be transported to base 1 directly or indirectly.

Blue Mary defines the safety of nexus i, R(i), as the following:

C_i and k are numeral constants which will be given in the input file.

Suppose for a fixed i, set T={P₁, P₂, P₃ ... P_w}, then x is a member of T if and only if S_x is i. Any two P_js must be different.

Now Blue Mary wants to modify at most M (0<= M <= N) S_i s, so that the safety of her base R(1) is maximized. To be a terran captive, also a great programmer, you must help her to solve this problem. Price is your life. Be careful! Blue Mary tells you that S₁ can't be modified. Don't ask your queen about the reason please.

Input

Ten test cases(given one after another, you have to process all!). For each test case:

The first line contains N, M and a real number k (0.3<= k <1). The second line contains N space separated integers S_i. The third line contains N positive real numbers C_i.

There is a single blank line between consecutive test cases.

Output

For each test case:

A single line - the maximized safety of nexus 1, rounded to two decimal places.

Example

Input:
4 1 0.5
2 3 1 3
10.0 10.0 10.0 10.0
[and 9 test cases more]

Output:
30.00
[and 9 test cases more]

Hint

Before modifying, the safety of the 4 bases are 22.8571, 21.4286,25.7143,10, respectively.

After modifying S₂ to 1, the safety of the 4 bases are 30, 25, 15, 10, respectively.