The 2008 Beijing Olympics are approaching, and the entire nation is preparing for this grand event. To host the Olympics efficiently and successfully, planning the logistics system is essential.
The logistics system consists of several logistics stations, numbered $1 \dots N$. Each logistics station $i$ has one and only one successor station $S_i$, but can have multiple predecessor stations. Goods at station $i$ that need further transport will be shipped to the successor station $S_i$. Obviously, a logistics station's successor cannot be itself. The logistics station numbered 1 is called the control station, and goods can be shipped to the control station from any logistics station. Note that the control station also has a successor station to facilitate the circulation of goods when necessary. In the logistics system, high reliability and low cost are the main design goals. For station $i$, we define its "reliability" $R(i)$ as follows:
Suppose logistics station $i$ has $w$ predecessor stations $P_1, P_2, \dots, P_w$, meaning these stations have $i$ as their successor. Then the reliability $R(i)$ of station $i$ satisfies the following equation:
$$R(i) = C_i + k \sum_{j=1}^{w} R(P_j)$$
where $C_i$ and $k$ are constant real numbers, both are strictly positive, and $k < 1$.
The reliability of the entire system is positively correlated with the reliability of the control station. Our goal is to modify the logistics system—that is, to change the successor stations of certain stations—so that the reliability of the control station $R(1)$ is as large as possible. However, due to budget constraints, at most $m$ stations' successors can be modified, and the successor of the control station cannot be modified. Therefore, the problem we face is how to modify the successors of at most $m$ stations to maximize the reliability of the control station $R(1)$.
Input
The first line contains two integers and one real number: $N, m, k$. $N$ represents the number of stations, $m$ represents the maximum number of successors that can be modified, and $k$ is the constant in the reliability definition.
The second line contains $N$ integers, $S_1, S_2, \dots, S_N$, which are the successor station numbers for each station.
The third line contains $N$ positive real numbers, $C_1, C_2, \dots, C_N$, which are the constants in the reliability definition.
Output
The output contains only one real number, the maximum possible $R(1)$, rounded to two decimal places.
Examples
Input 1
4 1 0.5 2 3 1 3 10.0 10.0 10.0 10.0
Output 1
30.00
Note
The original logistics system is shown in the left figure below. The reliabilities of the 4 logistics stations are 22.8571, 21.4286, 25.7143, and 10, respectively.
The optimal strategy is to change the successor of station 2 to station 1, as shown in the right figure. At this time, the reliabilities of the 4 stations are 30, 25, 15, and 10, respectively.
Constraints
The data for this problem has the following distribution:
| Test Case ID | $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~10 | $\le 60$ | $\le 60$ |
For all data, $m \le N \le 60$, $C_i \le 10^6$, $0.3 \le k < 1$. Please use double-precision floating-point numbers; there is no need to consider errors caused by this.