컴퓨터를 지켜라

컴퓨터는 여러 부품으로 이루어진다. 부품 하나라도 고장 나면 컴퓨터 전체가 멈춘다. 한 학기 치 예산을 학기 초에 한꺼번에 받았으니, 그 돈으로 예비 부품을 미리 사 두면 부품이 고장 났을 때 바로 갈아 끼울 수 있다.

부품이 고장 나는 횟수는 포아송 분포를 따른다. 부품 $i$가 시간 $t$ 동안 정확히 $k$번 고장 날 확률은 다음과 같다.

$P_i(k, t) = \frac{e^{-\lambda_i t}(\lambda_i t)^k}{k!}$

여기서는 한 학기만 보므로 $t = 1$로 고정하고, 식은 다음과 같이 줄어든다.

$P_i(k) = \frac{e^{-\lambda_i}\lambda_i^k}{k!}$

$\lambda_i$는 부품 $i$가 한 학기에 고장 나는 횟수의 기댓값이다. 서로 다른 부품이 고장 나는 사건은 독립이다.

부품 $i$의 예비를 $s_i$개 사 두면, 부품 $i$가 한 학기 동안 $s_i$번 이하로 고장 나는 한 컴퓨터는 계속 돌아간다. 예비 하나의 가격은 $r_i$이고, 예비를 사는 데 쓴 돈의 합은 예산 $b$를 넘을 수 없다. 컴퓨터가 학기 내내 멈추지 않을 확률은 부품마다 구한 확률의 곱이다.

예산 안에서 부품마다 예비를 몇 개씩 살지 정해서 이 확률을 최대로 만들어라.

첫째 줄에 테스트 케이스의 개수 $n$ ($1 \le n \le 50$)이 주어진다.

각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에 고장 날 수 있는 부품의 개수 $c$ ($1 \le c \le 500$)와 예산 $b$ ($0 \le b \le 500$)가 공백 하나를 사이에 두고 주어진다. 둘째 줄에 실수 $c$개가 주어진다. $i$번째 수는 부품 $i$가 한 학기에 고장 나는 횟수의 기댓값 $\lambda_i$ ($0.0 \le \lambda_i \le 5.0$)이다. 셋째 줄에 정수 $c$개가 주어진다. $i$번째 수는 부품 $i$의 예비 하나의 가격 $r_i$ ($1 \le r_i \le 100$)이다.

각 테스트 케이스마다 얻을 수 있는 최대 생존 확률을 소수점 아래 다섯째 자리까지 반올림해서 한 줄에 하나씩 출력한다.