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