올림픽 물류

베이징 2008 올림픽이 곧 열리고 나라 전체가 이 행사를 준비하고 있다. 대회를 효율적으로 운영하려면 물류 계획이 필수다.

물류 시스템에는 1번부터 N번까지 번호가 붙은 N개의 역이 있다. 각 역 i에는 후속 역 S_i가 정확히 하나 있고, 선행 역은 여러 개일 수 있다. 역 i는 후속 역 S_i에게 물자를 계속 보낸다. 역은 자기 자신을 후속 역으로 가질 수 없다. 1번 역은 관제 역이며, 다른 모든 역은 관제 역에 물자를 보낼 수 있다. 관제 역도 후속 역을 가지고 있어서 필요할 때 물자가 흐르게 한다. 이 시스템은 높은 신뢰성과 낮은 비용을 목표로 설계되었다. 역 i의 신뢰도 R(i)는 다음과 같이 정의한다.

역 i의 선행 역이 w개이고 이들을 P_1, P_2, ..., P_w라 하자. 각 P_j의 후속 역은 i이다. 이때

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

이며, 여기서 C_i와 k는 양의 실수 상수이고 k < 1이다.

전체 시스템의 신뢰도는 관제 역의 신뢰도에 직접 달려 있다. 목표는 최대 m개 역의 후속 역을 바꿔서 R(1)을 최대로 만드는 것이다. 예산 제약으로 후속 역은 최대 m개까지만 바꿀 수 있다. 관제 역의 후속 역은 바꿀 수 없다.

첫 줄에는 정수 N과 m, 그리고 실수 k가 주어진다. N은 역의 개수, m은 후속 역을 바꿀 수 있는 최대 개수, k는 신뢰도 식에 쓰이는 상수이다.

둘째 줄에는 각 역의 후속 역을 나타내는 정수 S_1, S_2, ..., S_N이 주어진다.

셋째 줄에는 양의 실수 C_1, C_2, ..., C_N이 주어진다.

R(1)의 최댓값을 실수 하나로 출력한다. 소수점 아래 둘째 자리까지 반올림한다.

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

배정밀도 실수를 사용하면 된다. 정밀도는 신경 쓰지 않아도 된다.