Card Collecting

Lately, a variety of free-to-play collectible card games have become popular. These card games usually have a collection of $n$ cards that the player wants to collect. The player first receives a starter pack of $s$ cards, which is guaranteed to contain no duplicates (they are all distinct). The player can then acquire new cards in two ways:

1. Trade any $d$ cards the player holds for one card of the player's choice. This is very quick, and in this problem we assume it takes no time.
2. Play games for an hour, and win a pack of $k$ cards with probability $p_i$, where $i$ is the number of distinct cards the player currently holds. Each card in the pack is chosen independently and uniformly at random from the entire collection of $n$ cards, so the pack may contain duplicates.

The advantage of a larger collection is that the player has a higher chance of winning a pack, and so earns random cards more quickly.

Stingy Larry plays card games of this type all the time. Larry just got a copy of such a game, is about to open his starter pack of $s$ cards, and wants to complete the full collection of $n$ cards. Assuming that Larry manages his collection optimally, what is the shortest expected time to complete the collection?

The first line contains a single integer $T$ ($1 \le T \le 10$), the number of test cases.

The first line of each test case contains four integers $n$, $s$, $k$, and $d$: $n$ ($1 \le n \le 100$) is the total number of cards in the collection, $s$ ($0 \le s \le n$) is the number of cards in the starter pack, $k$ ($1 \le k \le 10$) is the number of cards in a pack, and $d$ ($1 \le d \le 100$) is the number of cards that must be traded for one new card.

The next line contains $n+1$ space-separated real numbers $p_0, p_1, \ldots, p_n$ ($0.01 \le p_i \le 1$), where $p_i$ is the probability of winning a pack after an hour of play while holding $i$ distinct cards. The $p_i$ are nondecreasing.

For each test case, print on its own line the shortest expected time, in hours, for Larry to complete the collection, rounded to exactly six digits after the decimal point.

In the first test case of the example, Larry needs to play four hours on average to win the single card he needs to complete his collection.