TRANSP1 - Transportation

no tags 

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 Si.(i and Si 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:

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

Suppose for a fixed i, set T={P1, P2, P3 ... Pw}, then x is a member of T if and only if Sx is i. Any two Pjs must be different.

Now Blue Mary wants to modify at most M (0<= M <= N) Si 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 S1 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 Si. The third line contains N positive real numbers Ci.

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 S2 to 1, the safety of the 4 bases are 30, 25, 15, 10, respectively.



Added by:Fudan University Problem Setters
Date:2008-08-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Chinese National Olympiad in Informatics 2008, Day 2