AT_abc470_e [ABC470E] Concentration

> 高橋君は神経衰弱のような $ 1 $ 人ゲームで遊んでいます。 $ 2N $ 枚のカードがあります。カードの表には数が $ 1 $ つ書かれており、カードの裏には何も書かれていません。 $ 1 \leq i \leq N $ を満たす各 $ i $ について、 $ A_i $ が書かれたカードはちょうど $ 2 $ 枚あります。( $ A_i $ は相異なります) 高橋君はこれらのカードを使って次の手順でゲームを行います。 - $ 2N $ 枚のカードを裏向きの状態でシャッフルし、場に並べる。 - **ライフ** を $ L $ 、**スコア** を $ 0 $ とする。 - ライフが $ 0 $ になるか、場のカードがなくなるまで以下を繰り返す。 - 場の裏向きのカードを $ 1 $ 枚選び表にし、書かれている数 $ X $ を確認する。 - 場の裏向きのカードを $ 1 $ 枚選び表にし、書かれている数 $ Y $ を確認する。 - $ X=Y $ のとき、その $ 2 $ 枚を場から取り除き、スコアを $ X $ 増やす。 - $ X\neq Y $ のとき、 $ 2 $ 枚のカードを再び裏向きに戻し、ライフを $ 1 $ 減らす。 高橋君がゲーム時のスコアを最大化するように最適に行動したときの、ゲーム終了時のスコアの期待値を求めてください。 ゲームに関するより厳密な説明は以下の通りです。 - 高橋君は、以下に述べるこのゲームのルールを知っている。 - 高橋君は $ A_1,\dots,A_N $ の値を知っている。 - 長さ $ 2N $ の列 $ (A_1,A_1,A_2,A_2,\ldots,A_N,A_N) $ の並び替えを一様ランダムに $ 1 $ つ取り $ B $ とする。 - 最初、高橋君は $ B $ のどの値も知らない。高橋君は一度知った $ B_i $ の値をそれ以降完全に記憶する。 - ライフを $ L $ 、スコアを $ 0 $ 、 $ S $ を $ \{1,2,3,\ldots,2N\} $ とする。これらの値を高橋君は常に知っている。 - ライフが $ 0 $ になるか、 $ S $ が空になるまで以下を繰り返す。 - 高橋君はこの時点までに得られた情報に基づいて $ S $ から要素を $ 1 $ つ選択し $ i $ とする。 - $ B_i $ の値が公開され、高橋君はその値を知る。 - 高橋君はこの時点までに得られた情報( $ B_i $ の値を含む)に基づいて $ S\setminus\{i\} $ から要素を $ 1 $ つ選択し $ j $ とする。 - $ B_j $ の値が公開され、高橋君はその値を知る。 - $ B_i=B_j $ ならば、 $ S $ から $ i,j $ を取り除き、スコアに $ B_i $ を加算する。 - $ B_i \neq B_j $ ならば、 ライフを $ 1 $ 減らす。 - 高橋君は、ゲーム終了時のスコアの期待値を最大化するように、最適に行動する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ L $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを出力せよ。 真の解との絶対誤差または相対誤差が $ 10^{-5} $ 以下であれば正解として扱われる。

### Sample Explanation 1 例えばゲームは次のように進行します。 $ 6 $ 枚のカードを区別するために、`A`, `B`, `C`, `D`, `E`, `F` と呼ぶことにします。 - ライフ $ 2 $ 、スコア $ 0 $ でゲームを始める。 - カード `A` を表にする。 $ 3 $ が書かれている。 - カード `B` を表にする。 $ 2 $ が書かれている。 - 異なる数が書かれているので、 $ 2 $ 枚とも裏に戻し、ライフを $ 1 $ 減らして $ 1 $ とする。 - カード `C` を表にする。 $ 3 $ が書かれている。 - カード `A` を表にする。 $ 3 $ が書かれている。 - 同じ数が書かれているので、 $ 2 $ 枚とも場から取り除き、スコアを $ 3 $ 増やして $ 3 $ とする。 - カード `D` を表にする。 $ 1 $ が書かれている。 - カード `E` を表にする。 $ 2 $ が書かれている。 - 異なる数が書かれているので、 $ 2 $ 枚とも裏に戻し、ライフを $ 1 $ 減らして $ 0 $ とする。 - ライフが $ 0 $ となったのでゲームを終了する。スコアは $ 3 $ である。 この進行におけるカード `C` を表にした直後の時点で、高橋君は「カード `C` の表に $ 3 $ が書かれていたことを受けて、既に知っている $ 3 $ が書かれているもう $ 1 $ 枚のカード `A` を表にする」という判断が可能であることに注意してください。 ### Constraints - $ 1 \leq N \leq 200 $ - $ 1 \leq L \leq 200 $ - $ 1 \leq A_1 < A_2 < \dots < A_N \leq 10^5 $ - 入力される値は全て整数