Jūs esate pagrindinis „Tikimybių taurės“ (angl. „Probability Open“) turnyro organizatorius. Turnyre dalyvauja 2^N žaidėjų, kurių kiekvienas turi stiprumo reikšmę S_i. Vienas iš šių žaidėjų yra jūsų favoritas – žaidėjas K.
Jūs turite kiekvienam žaidėjui priskirti bet kurią iš
2^N pradinių pozicijų standartinėje vieno minuso sistemos (angl. single-elimination) turnyro lentelėje. Bet kurioje kovoje tarp žaidėjo
A ir žaidėjo
B tikimybė, kad žaidėjas
A laimės, yra:
P(A \text{ laimi}) = \frac{S_A}{S_A + S_B}
Jūsų tikslas – taip sudėlioti pradinę turnyro lentelę, kad žaidėjo
K tikimybė laimėti visą turnyrą būtų maksimali.
Input
Pirmoje eilutėje pateiktas sveikasis skaičius N (1 \le N \le 10), kur 2^N nurodo žaidėjų skaičių.
Antroje eilutėje pateikta 2^N sveikųjų skaičių S_0, S_1, \dots, S_{2^{N-1}} (1 \le S_i \le 100).
Trečioje eilutėje pateiktas sveikasis skaičius K (0 \le K < 2^N) – jūsų favorito indeksas stiprumo sąraše.
Output
Išveskite vieną dešimtainę reikšmę: didžiausią įmanomą tikimybę, kad žaidėjas K laimės turnyrą. Jūsų atsakymas bus laikomas teisingu, jei jo absoliutinė arba santykinė paklaida neviršija 10^{-6}.
Galima naudoti bet kokį standartinį skaičių formatą (įskaitant eksponentinį).
Examples
| standard input | standard output |
|---|
| 1
1 1
0
| 0.5
|
| 2
1 2 3 4
0
| 0.0738095
|