Olympic Logistics

The Beijing 2008 Olympics is about to open, and the entire nation is preparing for this event. Careful logistics planning is essential for running the Games efficiently.

The logistics system has N stations numbered 1 to N. Each station i has exactly one successor station S_i, and can have many predecessor stations. Station i continuously delivers materials to S_i. A station cannot be its own successor. Station 1 is the control station, and any other station can deliver materials to it. The control station also has a successor station, which lets materials flow when needed. The system is designed for high reliability and low cost. For station i, the reliability R(i) is defined as follows.

Let station i have w predecessor stations P_1, P_2, ..., P_w, each of which has i as its successor. Then

$R(i) = C_i + k \sum_{j=1}^{w} R(P_j)$

where C_i and k are positive real constants, and k < 1.

The reliability of the whole system depends directly on the reliability of the control station. Your goal is to maximize R(1) by changing the successors of at most m stations. The budget allows at most m changes. The successor of the control station cannot be changed.

The first line contains two integers N and m, followed by a real number k. N is the number of stations, m is the maximum number of successor stations that may be changed, and k is the constant used in the reliability formula.

The second line contains N integers S_1, S_2, ..., S_N, the successor of each station.

The third line contains N positive real numbers C_1, C_2, ..., C_N.

Print one real number, the maximum possible value of R(1), rounded to 2 decimal places.

$m \le N \le 60$, $C_i \le 10^6$, $0.3 \le k < 1$.

Use double precision real numbers. You do not need to worry about precision.