코어 훈련 (모든 코어)

AI 하나가 성격이 제각각인 코어 $N$개로 돌아간다. 코어도 사람처럼 딴짓을 하거나 망가지거나 아예 일을 거부한다. $i$번 코어가 제대로 작동할 확률은 $P_i$다. 코어가 $K$개 이상 제대로 작동하면 AI도 제대로 작동하고, 그렇지 않으면 AI는 엉뚱한 짓을 시작한다.

그래서 코어 몇 개를 훈련시켜 더 믿을 만하게 만들려고 한다. 쓸 수 있는 훈련 단위는 모두 합쳐 $U$다. $i$번 코어에 $X$만큼 쓰면 그 코어의 성공 확률이 $X$만큼 올라간다. 단위는 실수 값으로 원하는 대로 쪼개 나눠 줄 수 있고, 한 단위도 받지 못하는 코어가 있어도 된다. 물론 성공 확률은 $1$을 넘길 수 없다.

훈련 단위를 최적으로 배분했을 때 AI가 제대로 작동할 확률을 구하라.

이 문제에서는 항상 $K = N$이다. 즉 코어가 하나라도 실패하면 AI는 제대로 작동하지 않는다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어지고, 각 케이스는 세 줄이다. 첫 줄에는 정수 $N$과 $K$가 주어진다. $N$은 코어 수, $K$는 AI가 제대로 작동하는 데 필요한 최소 성공 코어 수다. 둘째 줄에는 훈련 단위의 총량 $U$가 주어진다. 셋째 줄에는 수 $N$개가 주어지고, 그중 $i$번째 값이 $i$번 코어의 성공 확률 $P_i$다. $U$와 $P_i$는 모두 소수점 아래 넷째 자리까지 적혀 있다.

제한

• $1 \le T \le 100$
• $1 \le N \le 50$
• 모든 $i$에 대해 $0.0000 \le P_i \le 1.0000$
• $0.0000 \le U \le N - \sum_{i=1}^{N} P_i$ (쓸 수 있는 양보다 많은 훈련 단위는 주어지지 않는다)
• $K = N$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 훈련 단위를 최적으로 배분했을 때 AI가 제대로 작동할 확률이다.

$y$는 소수점 아래 일곱째 자리에서 반올림해 소수점 아래 여섯 자리로 출력한다. 버리는 부분이 정확히 절반이면 올린다. 끝자리가 0이어도 여섯 자리를 모두 적는다. 확률이 $1$이면 1.000000, $1/4$이면 0.250000으로 출력한다.

첫 번째 예제의 첫 케이스에서는 훈련 단위가 넉넉해서 코어 네 개를 모두 확률 $1$까지 올릴 수 있다. 그래서 답은 $1$이다.

첫 번째 예제의 둘째 케이스에서는 코어 두 개가 모두 성공해야 하므로 양쪽에 단위를 나눠 준다. 각각 $0.5$로 올리는 것이 최선이고 확률은 $0.5 \times 0.5 = 0.25$다. 한쪽을 $0.9$, 다른 쪽을 $0.1$로 만들면 $0.09$에 그친다.

두 번째 예제의 셋째 케이스에서는 단위 $0.2$를 전부 낮은 쪽 코어에 주어 $0.1$을 $0.3$으로 올린다. 답은 $0.3 \times 0.9 = 0.27$이다. 단위를 전부 높은 쪽 코어에 주면 확률이 $1$을 넘을 수 없어 $0.1 \times 1.0 = 0.1$이 되고, 절반씩 나누면 $0.2 \times 1.0 = 0.2$가 된다.