카드 수집

요즘 무료로 즐기는 수집형 카드 게임이 여러 종류 인기를 끌고 있다. 이런 게임에는 보통 플레이어가 모으고 싶어 하는 카드가 모두 $n$종 있다. 플레이어는 처음에 $s$장짜리 스타터 팩을 받는데, 이 팩에는 중복된 카드가 없다(모두 서로 다른 카드다). 그 뒤 플레이어는 다음 두 가지 방법으로 새 카드를 얻을 수 있다.

1. 가지고 있는 카드 중 아무 카드 $d$장을 내주고 원하는 카드 1장으로 교환한다. 교환은 매우 빨리 끝나므로 이 문제에서는 시간이 전혀 걸리지 않는다고 가정한다.
2. 게임을 1시간 플레이한다. 그러면 확률 $p_i$로 카드 $k$장이 든 팩을 얻는다. 여기서 $i$는 플레이어가 현재 가지고 있는 서로 다른 카드의 종류 수다. 팩의 각 카드는 전체 $n$종 가운데 독립적이고 균일하게 무작위로 정해진다. 따라서 팩 안에 중복된 카드가 있을 수도 있다.

모은 카드의 종류가 많을수록 팩을 얻을 확률이 높아지므로 무작위 카드를 더 빨리 얻는다.

구두쇠 래리는 이런 카드 게임을 늘 즐긴다. 래리는 방금 이런 게임을 하나 새로 구했고, 이제 $s$장짜리 스타터 팩을 막 열려고 한다. 래리의 목표는 $n$종의 카드를 모두 모으는 것이다. 래리가 카드를 최적으로 관리할 때, 수집을 완성하는 데 걸리는 시간의 기댓값의 최솟값을 구하라.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 정수 네 개 $n$, $s$, $k$, $d$가 주어진다. $n$ ($1 \le n \le 100$)은 카드의 전체 종류 수, $s$ ($0 \le s \le n$)는 스타터 팩의 카드 수, $k$ ($1 \le k \le 10$)는 팩 하나에 든 카드 수, $d$ ($1 \le d \le 100$)는 새 카드 1장을 얻기 위해 내줘야 하는 카드 수다.

다음 줄에는 공백으로 구분된 실수 $n+1$개 $p_0, p_1, \ldots, p_n$ ($0.01 \le p_i \le 1$)이 주어진다. $p_i$는 서로 다른 카드를 $i$종 가지고 있을 때 1시간 플레이해서 팩을 얻을 확률이다. $p_i$는 감소하지 않는다.

각 테스트 케이스마다 래리가 수집을 완성하는 데 걸리는 시간의 기댓값의 최솟값을 시간 단위로 한 줄에 하나씩 출력한다. 값은 소수점 아래 여섯째 자리까지 반올림하여 출력한다.

예제의 첫 번째 테스트 케이스에서 래리는 수집을 완성하는 데 필요한 카드 1장을 얻기 위해 평균 4시간을 플레이해야 한다.