You are the mastermind behind the "Probability Open" tournament. There are
2^N players, each with a strength value
S_i. One of these players is your personal favorite, Player
K.
You have the authority to assign each player to any of the
2^N starting slots in a standard single-elimination tournament bracket. In any match between Player
A and Player
B, the probability of Player
A winning is:
P(A \text{ wins}) = \frac{S_A}{S_A + S_B}
Your goal is to arrange the initial bracket such that the probability of Player
K winning the entire tournament is maximized.
Input
The first line contains an integer N (1 \le N \le 10), where 2^N represents amount of players.
The second line contains 2^N integers S_0, S_1, \dots, S_{2^{N-1}} (1 \le S_i \le 100).
The third line contains an integer K (0 \le K < 2^N), the index of your favorite player in the strength list.
Output
Print a single decimal value: the maximum possible probability of Player K winning. Your answer is considered correct if its absolute or relative error does not exceed 10^{-6}.
Any standard notation (including scientific) is acceptable.
Examples
| standard input | standard output |
|---|
| 1
1 1
0
| 0.5
|
| 2
1 2 3 4
0
| 0.0738095
|