AT_tenka1_2016_final_f Blind Purchase

[problemUrl]: https://atcoder.jp/contests/tenka1-2016-final/tasks/tenka1_2016_final_f 天下一トイズは、フィギュアの安売りで有名な玩具店です。この店は $ N $ 種類のフィギュアを取り扱っており、この問題ではそれらをフィギュア $ 1 $, フィギュア $ 2 $, ..., フィギュア $ N $ と呼びます。 店の $ 1 $ 階ではフィギュアが個別に売られており、フィギュア $ i $ $ (1\ ≦\ i\ ≦\ N) $ は $ 1 $ 個 $ P_i $ 円で買うことができます。 店の $ 2 $ 階にはフィギュアの自動販売機が置かれており、この機械に $ G $ 円を入れると、$ N $ 種類すべてのフィギュアから等確率で $ 1 $ 個が出ます。この機械はフィギュアを自動で製造するので、各フィギュアが出る確率は常に $ 1/N $ です。 あなたは天下一トイズを訪れました。あなたの目的は、この店で $ N $ 種類すべてのフィギュアをそれぞれ $ 1 $ 個以上入手することです。店の $ 1 $ 階と $ 2 $ 階をどのような順序で何度利用してもかまいません。また、使える金額に上限はありません。すべてのフィギュアを入手するまでの消費金額の期待値を最小化する戦略をとったとき、その期待値はいくらになるでしょうか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ G $ $ P_1 $ $ P_2 $ ... $ P_N $

すべてのフィギュアを入手するまでの消費金額の期待値を最小化する戦略をとったときの、消費金額の期待値を出力せよ。 出力は、ジャッジの出力との絶対誤差または相対誤差が $ 10^{-6} $ 以下であるとき、正解とみなされる。

### 制約 - $ 2\ ≦\ N\ ≦\ 36 $ - $ 1\ ≦\ G\ ≦\ 36 $ - $ 1\ ≦\ P_i\ ≦\ 36 $ - 入力値はすべて整数である。 ### Sample Explanation 1 フィギュアが $ 2 $ 種類あり、店の $ 1 $ 階ではフィギュア $ 1 $ を $ 5 $ 円、フィギュア $ 2 $ を $ 6 $ 円で買えます。また、店の $ 2 $ 階の自動販売機に $ 4 $ 円を入れると、等確率でどちらかのフィギュアが出ます。 ここでの最適な戦略は、「まず自動販売機でフィギュアを $ 1 $ 個買い、出なかった方のアイテムを $ 1 $ 階で買う」というものです。この戦略をとったときの消費金額は、自動販売機から出たフィギュアがフィギュア $ 1 $ なら $ 4\ +\ 6\ =\ 10 $, フィギュア $ 2 $ なら $ 4\ +\ 5\ =\ 9 $ です。したがって、この戦略での消費金額の期待値は $ 1/2\ ×\ 10\ +\ 1/2\ ×\ 9\ =\ 19/2 $ となります。どのような戦略をとっても、この期待値が $ 19/2 $ より小さくなることはありません。 ### Sample Explanation 2 自動販売機の価格設定が高いため、すべてのフィギュアを $ 1 $ 階で買うのが最適です。 ### Sample Explanation 3 自動販売機の価格設定が低いため、すべてのフィギュアが出るまで自動販売機からフィギュアを買い続けるのが最適です。