Ігрові реліквії#9586

Ігрові реліквії

1 секунда

128 мегабайтів

Легка

Кіберспорт - це змагальний вид спорту, що використовує відеоігри. Dota 2 є однією з найпопулярніших ігор у цій сфері. Нещодавно вийшла нова гра - Dota 3. У Dota 3 гравці можуть купувати реліквії для своїх героїв. Реліквії - це лічильники, які відстежують дії та статистику героя в грі.

Глорія захоплюється грою в Dota 3 і хоче придбати всі $n$ доступних реліквій для свого улюбленого героя.

Реліквії можна купити за внутрішньоігрову валюту, яка називається уламками. Кожна реліквія має свою ціну - $c_{i}$ c_i уламків за $i$ -у реліквію. Гравець може придбати реліквію одним із наступних способів:

Заплатити $c_{i}$ c_i уламків, щоб купити $i$ -у реліквію;
Заплатити $x$ уламків і випадковим чином отримати одну з усіх наявних $n$ реліквій. Ймовірність отримання кожної реліквії однакова. Якщо випадає дублікат, реліквія переробляється, і гравцеві повертається $x /2$ уламків.

Глорія прагне придбати всі $n$ реліквій. Допоможіть їй мінімізувати очікувану кількість уламків, яку вона витратить на покупку всіх реліквій.

Вхідні дані

Перша строка містить два цілих числа $n$ і $x$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100, $1 \leq x \leq 10000$ 1 \leq x \leq 10000) - кількість реліквій та вартість отримання випадкової реліквії.

Друга строка містить $n$ цілих чисел $c_{1}, c_{2}, \dots, c_{n}$ c_1, c_2, \ldots, c_n ( $x \leq c_{i} \leq 10000$ x \leq c_i \leq 10000, $\sum c_{i} \leq 10000$ \sum c_i \leq 10000) - ціни на $n$ реліквій.

Вихідні дані

Виведіть одне дійсне число - мінімальну очікувану кількість уламків, яку Глорія повинна витратити, щоб купити всі реліквії. Абсолютна або відносна похибка не повинна перевищувати $1 0^{- 9}$ 10^{-9}.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі оптимальна стратегія - випадковим чином отримати одну з двох реліквій, заплативши $20$ уламків. Далі можливі два сценарії.

Перший сценарій: Глорія отримує першу реліквію. Потім вона продовжує отримувати випадкові реліквії, поки не отримає другу. Очікувана кількість уламків у цьому випадку складе $20 + 30 = 50$ 20 + 30 = 50.

Другий сценарій: Глорія спочатку отримує другу реліквію. Тоді вигідніше купити першу реліквію за $25$ уламків, тому очікувана кількість уламків у цьому випадку складе $20 + 25 = 45$ 20 + 25 = 45. Таким чином, очікувана кількість уламків, які потрібно витратити, становить $(50 + 45) /2 = 47.5$ (50 + 45) / 2 = 47.5.