코어 훈련 (Small2)

대회 문제를 만드는 일은 어렵다. 그래서 새로운 아이디어를 대신 떠올려 줄 인공지능을 만들었다. 인공지능을 최대한 창의적으로 만들려고 성격이 제각각인 코어 $N$개를 붙여 놓았다. 그런데 사람이 그렇듯 코어도 한눈을 팔거나 망가지거나 일을 거부하기도 한다. $i$번 코어가 제대로 작동할 확률은 $P_i$이다. 코어가 $K$개 이상 제대로 작동하면 인공지능도 제대로 작동한다. 그렇지 않으면 인공지능은 사악해져서 자기가 설계한 고약한 퍼즐의 미로에 우리를 가둘 것이다. 대회에 무슨 짓을 할지도 모른다. 어려운 확률 문제만 잔뜩 낼 수도 있다.

이런 사태를 막으려고 코어를 하나 이상 훈련시켜 신뢰도를 높이기로 했다. 쓸 수 있는 훈련 단위는 모두 $U$만큼이다. $i$번 코어에 $X$만큼 쓰면 그 코어의 성공 확률이 $X$만큼 올라간다. 훈련 단위는 원하는 대로 나눠 줄 수 있고, 하나도 받지 못하는 코어가 있어도 된다. 물론 코어의 성공 확률을 $1$보다 크게 올릴 수는 없다.

인공지능이 제대로 작동할 확률이 가장 커지도록 훈련 단위를 배분했을 때, 그 확률은 얼마인가?

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지고, 각 테스트 케이스는 세 줄로 이루어진다.

첫째 줄에는 두 정수 $N$과 $K$가 주어진다. $N$은 코어의 개수이고, $K$는 인공지능이 제대로 작동하기 위해 성공해야 하는 코어의 최소 개수이다. 둘째 줄에는 훈련 단위의 양을 나타내는 유리수 $U$가 주어진다. 셋째 줄에는 유리수 $N$개가 주어지며, 그중 $i$번째 수 $P_i$는 $i$번 코어가 제대로 작동할 확률이다. $U$와 모든 확률은 소수점 아래 넷째 자리까지 정확히 주어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 50$
• $1 \le K \le N$
• 모든 $i$에 대해 $0.0000 \le P_i \le 1.0000$
• $0.0000 \le U \le N - (P_1 + P_2 + \dots + P_N)$ (쓸 수 있는 양보다 많은 훈련 단위가 주어지는 일은 없다)

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 훈련 단위를 최적으로 배분했을 때 인공지능이 제대로 작동할 확률이다. $y$는 소수점 아래 일곱째 자리에서 반올림해 소수점 아래 여섯 자리로 출력한다. 예를 들어 확률이 $0.25$이면 0.250000을, $1$이면 1.000000을 출력한다.

예제의 첫 번째 테스트 케이스에서는 모든 코어의 성공 확률을 1까지 올릴 만큼 훈련 단위가 넉넉하므로 인공지능은 반드시 제대로 작동한다.

두 번째 테스트 케이스에서는 코어 두 개가 모두 성공해야 하므로 두 코어 모두에 훈련 단위를 나눠 줘야 한다. 각각 $0.5$까지 올리는 것이 최선이고, 이때 확률은 $0.5 \times 0.5 = 0.25$이다. 다른 배분은 모두 이보다 나쁘다. 한쪽을 $0.9$로, 다른 쪽을 $0.1$로 올리면 확률은 $0.09$에 그친다.

세 번째 테스트 케이스에서는 쓸 훈련 단위가 없고, 코어 두 개 중 하나만 성공해도 된다. 인공지능이 제대로 작동하지 않는 경우는 두 코어가 모두 실패할 때뿐이며 그 확률은 $(1 - 0.9) \times (1 - 0.8) = 0.02$이다. 따라서 답은 $1 - 0.02 = 0.98$이다.

네 번째 테스트 케이스에서는 훈련 단위를 모두 두 번째 코어에 몰아주는 것이 최선이다. 그러면 적어도 하나가 성공할 확률이 $1 - (0.6 \times 0.4) = 0.76$이 된다. 다른 선택은 모두 이보다 못하다. 첫 번째 코어에 모두 주면 $0.75$, 두 코어에 똑같이 나눠 주면 $0.7525$이다.