AT_tkppc4_2_h 打鍵戦争

[problemUrl]: https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_h 現在のパ研では、「打鍵戦争」というゲームが流行っています。パ研には $ N $ 人の部員がいますが、その中から「打鍵戦争」という大会に $ K $ $ (2K\ \leq\ N) $ 人の代表選手を出すことになりました。 各部員には、「打鍵力」という値が定まっており、部員 $ i $ の打鍵力は $ A_i $ で、この値が等しいような部員の組は存在しません。 現在パ研では、「打鍵力」の**小さい**方から $ K $ 人が「代表候補」として選ばれています。 パ研の主将であるあなたは、以下の操作を $ 0 $ 回以上行います。 - その時点で代表候補である部員 $ i $、代表候補でない部員 $ j $ を自由に選び、対戦させる。 - 部員 $ i $ は確率 $ \frac{A_i}{A_i+A_j} $ で勝ち、部員 $ j $ は確率 $ \frac{A_j}{A_i+A_j} $ で勝つ。 - その時点で代表候補である部員 $ i $ が勝った場合何も起こらない。 - その時点で代表候補でない部員 $ j $ が勝った場合、部員 $ j $ が新たに代表候補となり、部員 $ i $ は代表候補から外れる。 あなたが対戦をさせるのをやめた時点で代表候補である部員たちが、そのまま代表選手となります。 あなたは、できるだけ少ない回数の対戦を行うことで、代表選手の打鍵力の和を最大化したいと思っています。対戦回数の期待値を最小化するように対戦させたとき、代表選手の打鍵力の和が最大になるまで何回の対戦が必要でしょうか。その期待値を求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ > $ A_1 $ $ A_2 $ $ ... $ $ A_{N-1} $ $ A_N $

対戦回数の期待値の最小値を出力してください。 絶対誤差または相対誤差が $ 10^{-9} $ 以内ならば正解となります。

### 制約 - 入力は全て整数である。 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ 2K\ \leq\ N $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ A_i\ \neq\ A_j(i\ \neq\ j) $