問題文

天下一トイズは、フィギュアの安売りで有名な玩具店です。この店は N 種類のフィギュアを取り扱っており、この問題ではそれらをフィギュア 1, フィギュア 2, ..., フィギュア N と呼びます。

店の 1 階ではフィギュアが個別に売られており、フィギュア i (1 ≦ i ≦ N) は 1 個 P_i 円で買うことができます。

店の 2 階にはフィギュアの自動販売機が置かれており、この機械に G 円を入れると、N 種類すべてのフィギュアから等確率で 1 個が出ます。この機械はフィギュアを自動で製造するので、各フィギュアが出る確率は常に 1/N です。

あなたは天下一トイズを訪れました。あなたの目的は、この店で N 種類すべてのフィギュアをそれぞれ 1 個以上入手することです。店の 1 階と 2 階をどのような順序で何度利用してもかまいません。また、使える金額に上限はありません。すべてのフィギュアを入手するまでの消費金額の期待値を最小化する戦略をとったとき、その期待値はいくらになるでしょうか？

制約

• 2 ≦ N ≦ 36
• 1 ≦ G ≦ 36
• 1 ≦ P_i ≦ 36
• 入力値はすべて整数である。

入力例 1

2 4
5 6

出力例 1

9.5

フィギュアが 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 より小さくなることはありません。

入力例 2

3 10
5 6 7

出力例 2

18.0

自動販売機の価格設定が高いため、すべてのフィギュアを 1 階で買うのが最適です。

入力例 3

3 1
5 6 7

出力例 3

5.5

自動販売機の価格設定が低いため、すべてのフィギュアが出るまで自動販売機からフィギュアを買い続けるのが最適です。

入力例 4

10 2
3 3 3 3 5 5 5 7 7 10

出力例 4

36.830952380952381