National Olympiad in Informatics, China, 2008

The Beijing 2008 Olympics is about to open, and the entire nation is preparing for this grand event. To maximize efficiency when setting up and hosting a successful Olympics, the planning of logistics is essential.

The logistics system consists of ~N~ total stations numbered from ~1~ to ~N~. Each station ~i~ has exactly one successor station ~S_i~, but can have many predecessor stations. Station ~i~ needs to continuously deliver materials to successor station ~S_i~. Obviously, a station's successor station cannot be itself. Station ~1~ is known as the control station, and any other station can deliver materials to it. Note that the control station also has its own successor station to permit the flow of materials when necessary. In the design of this logistics system, high reliability and low costs are the main objectives. So for station ~i~, we can define its "reliability" ~R(i)~ as follows:

Let station ~i~ have ~w~ predecessor stations ~P_1, P_2, \dots, P_w~, meaning that ~i~ is the sole successor of each of these stations. Then, station ~i~'s reliability ~R(i)~ is given by the following formula:

$$\displaystyle 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 entire logistics system is directly based on the reliability of the control station. Our goal is to maximize the control station's reliability value ~R(1)~ by modifying the successor stations of some other stations. However, our budget is also limited – we may only modify at most ~m~ successor stations. Furthermore, the successor of the control station cannot be modified. Thus, the overall problem we face is to maximize the control station's reliability ~R(1)~ by changing the successors of no more than ~m~ stations.

Input Specification

The first line of input contains two integers ~N~ and ~m~, followed by one real number ~k~. ~N~ represents the number of stations, ~m~ represents the maximum number of successor stations that may be changed, and ~k~ is the constant used in the definition of the reliability formula.
The second line contains ~N~ integers ~S_1, S_2, \dots, S_N~, representing the successor stations of each station.
The third line contains ~N~ positive real numbers ~C_1, C_2, \dots, C_N~, representing the constant values used in the reliability formula.

Output Specification

The output should contain one real number, the maximum possible value of ~R(1)~ rounded and displayed to ~2~ decimal places.

Sample Input

4 1 0.5
2 3 1 3
10.0 10.0 10.0 10.0

Sample Output

30.00

Explanation

The original logistics system is depicted in the left figure below. There are ~4~ stations with reliability values ~22.8571~, ~21.4286~, ~25.7143~, and ~10~, respectively.

The best solution is to modify the successor of station ~2~ to station ~1~, as depicted in the right figure above. The new reliability values of the stations are ~30~, ~25~, ~15~, and ~10~, respectively.

Constraints

Test Case	~N~	~m~
~1~	~\le 6~	~\le 6~
~2~	~\le 12~	~\le 12~
~3~	~\le 60~	~0~
~4~	~\le 60~	~1~
~5~	~\le 60~	~N-2~
~6~ to ~10~	~\le 60~	~\le 60~

For all of the test cases, ~m \le N \le 60~, ~C_i \le 10^6~, and ~0.3 \le k < 1~. Please use double precision real numbers; there is no need to worry about their precision.

Problem translated to English by Alex.