Expected Duel Damage

In this problem, there are four types of playing cards: heart \(A\), heart \(K\), spade \(A\) and spade \(K\). Xiao Q has \(n\) spade cards and \(m\) heart cards. Among the spade cards, exactly \(u\) are \(A\)'s; among the heart cards, exactly \(v\) are \(A\)'s (and the remaining \(m-v\) cards are \(K\)'s). The opponent has \(k\) cards. For the opponent's cards, the probability that the \(i\)th card has point \(A\) is given by \(a_i\) (which may be different for different \(i\)).

The game proceeds as follows. As long as Xiao Q has at least one heart card (either heart \(A\) or heart \(K\)) he must perform the following operation:

1. Randomly (with equal probability) discard one heart card from his hand and then initiate a duel with the opponent.
2. If he has no heart card, his turn ends.

The duel is carried out as follows (starting with the opponent):

1. The current player looks at his hand of cards for the duel. If he has at least one card with point \(A\) (for the opponent, any card in his hand that is actually an \(A\); for Xiao Q his duel hand consists of his spade \(A\)'s as well as any remaining heart \(A\)'s after his random discard), then he must randomly discard one such \(A\) card.
2. If he does not have any \(A\) card, he receives \(1\) point of damage and the duel terminates immediately.

The duel alternates turns. Note that during the duel, each discarded card is removed permanently from that player's hand. In particular, for Xiao Q his available \(A\) cards (for duels) come from his spade \(A\)'s (\(u\) cards) and his heart \(A\)'s (\(v\) cards) that were not discarded in the initiation phase. When initiating a duel, a random heart card is discarded. Thus, if the discarded card is a heart \(A\) (which happens with probability \(\frac{v}{m}\) at the start of his first duel), his available duel \(A\) count will be \(u+v-1\); otherwise (with probability \(\frac{m-v}{m}\)) his available duel \(A\) count remains \(u+v\).

The outcome of a duel is determined by the following observation. Suppose that at the start of the duel the opponent has \(X\) \(A\) cards and Xiao Q has \(Y\) available \(A\) cards (after the initiation discard as described). The duel proceeds in alternating turns with the opponent going first. In each turn if the current player has at least one \(A\) he discards one; otherwise, he receives 1 damage and the duel ends. It is easy to see (by simulating the rounds) that:

• If \(X \le Y\), then the opponent will be the first to fail to discard an \(A\) (receiving 1 damage).
• If \(X > Y\), then Xiao Q will fail, receiving no damage (and the opponent will discard some \(A\)'s but remain with some \(A\)'s).

Xiao Q will continue initiating duels as long as he has heart cards. Notice that whenever he wins a duel (i.e. when the opponent fails because \(X \le Y\)), the opponent's duel hand becomes empty (\(X\) resets to \(0\)) and all subsequent duels will immediately cause 1 damage to the opponent (since the opponent will have no \(A\) cards to discard) as long as Xiao Q can still initiate a duel.

Thus, the overall process is as follows:

• Before the first duel, Xiao Q randomly discards one heart card. With probability \(\frac{m-v}{m}\) the discarded card is a heart \(K\) making his effective duel \(A\) count \(Y = u+v\), and with probability \(\frac{v}{m}\) it is a heart \(A\) making \(Y = u+v-1\).
• The opponent's initial number \(X\) of \(A\) cards is determined by his \(k\) cards; each card is an \(A\) independently with probability \(a_i\) (the \(i\)th card has probability \(a_i\)).
• If the duel results in victory for Xiao Q (i.e. if \(X \le Y\)), then not only does the duel inflict 1 damage on the opponent, but also the opponent's \(A\) count becomes \(0\) for all subsequent duels. Since Xiao Q will continue to initiate duels as long as he has heart cards, he will inflict 1 damage in each remaining duel. Hence, if the first duel is won, the total damage inflicted will be equal to the number of duels initiated (which is \(m\)).
• If the first duel is lost (i.e. \(X > Y\)), Xiao Q loses his available duel \(A\) cards and will fail in all subsequent duels, inflicting no additional damage on the opponent.

Therefore, the expected total damage the opponent takes during Xiao Q's turn is given by:

[ \text{Expected Damage} = m \times \Biggl[ \frac{m-v}{m} , F(u+v) + \frac{v}{m} , F(u+v-1) \Biggr], ]

where \(F(t)\) is the cumulative distribution function (CDF) of the number \(X\) of \(A\) cards in the opponent's hand, i.e.,

[ F(t) = \mathbb{P}(X \le t) = \sum_{j=0}^{\min{t,k}} ; \sum_{\substack{S\subseteq{1,2,\ldots,k}\|S|=j}} \Biggl(\prod_{i\in S}a_i\prod_{i\notin S}(1-a_i)\Biggr). ]

If \(t < 0\) we define \(F(t)=0\). Note that in particular if \(F(u+v)=1\) (i.e. the opponent has at most \(u+v\) \(A\) cards with probability 1) then every duel will inflict damage.

Your task is to compute the expected damage inflicted on the opponent during Xiao Q's turn.

inputFormat

The input consists of two lines.

The first line contains five integers:

(n), (m), (u), (v) and (k) — where (n) is the number of spade cards, (m) is the number of heart cards, (u) is the number of spade (A)'s, (v) is the number of heart (A)'s, and (k) is the number of cards in the opponent's hand.

</p>

The second line contains \(k\) real numbers \(a_1,a_2,\ldots,a_k\), where \(a_i\) denotes the probability that the \(i\)th opponent card is an \(A\). The probabilities are given with at most 6 digits after the decimal point.

outputFormat

Output a single real number — the expected damage inflicted on the opponent. Your answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

5 3 1 1 2
0.5 0.5

2.75

</p>