Богдан проти "хвостів"
ліміт часу на тест
1 second
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Побачивши хист Саші до закриття "хвостів", Богданчик також вирішив закрити всі борги з математики.

Всього він має $$$n$$$ завдань, кожне з яких має певну тему, позначену числом $$$a_i$$$.

Через те, що деякі теми повторюються, Богданчик виконує їх швидше, а саме:

- Якщо Богданчик виконує завдання даної теми вперше, то він використовує $$$x$$$ хвилин часу.
- Якщо ж він виконує його не вперше й останній раз коли він виконував цю тему, він витратив $$$q$$$ хвилин часу, то цього разу він витратить $$$\max(\lfloor \frac{q}{2} \rfloor,1)$$$ хвилин.

Знайдіть сумарний час у хвилинах, скільки він вирішуватиме домашнє завдання.

В умові позначення $$$\lfloor X \rfloor$$$ означає округлення вниз (до меншого цілого числа), наприклад $$$\lfloor 3.14 \rfloor = 3$$$, $$$\lfloor 3.9 \rfloor = 3$$$.

Вхідні дані

Перший рядок містить два цілі числа $$$n$$$ та $$$x$$$ ($$$1\le n\le 10^5$$$, $$$1\le x\le 10^9$$$) — кількість завдань з математики та як довго Богданчик вирішує домашнє завдання певної теми вперше.

Другий рядок містить $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — тема $$$i$$$-го завдання.

Вихідні дані

Виведіть одне число — кількість хвилин, які потрібні Богданчику для розв'язання всіх задач.

Система оцінки

У цій задачі існують умовні блоки. Якщо ваше рішення буде працювати правильно для певних обмежень, то воно отримуватиме певну кількість балів. Зверніть увагу, що оцінювання й досі потестове.

1. ($$$5$$$ балів): $$$x=1$$$;
2. ($$$15$$$ балів): $$$n\le 1000$$$;
3. ($$$15$$$ балів): $$$a_i\le n$$$;
4. ($$$15$$$ балів): $$$a_1=a_2=\dots=a_n$$$;
5. ($$$50$$$ балів): без додаткових обмежень.

Приклади

Вхідні дані

    2 21 2

Вихідні дані

    4

Вхідні дані

    3 42 2 2

Вихідні дані

    7

Пояснення

У першому тесті він виконає завдання з темою $$$1$$$ за $$$2$$$ хвилини, та завдання з темою $$$2$$$ за $$$2$$$ хвилини, сумарно витративши $$$4$$$ хвилини.

У другому тесті вперше виконуючи завдання з темою $$$2$$$ він витратить $$$4$$$ хвилини, повторно виконуючи він витратить $$$\max(\lfloor \frac{4}{2} \rfloor,1)=2$$$ хвилини, і, втретє виконуючи завдання з темою $$$2$$$, він витратить $$$\max(\lfloor \frac{2}{2} \rfloor,1)=1$$$ хвилину, тому сумарно він витратить $$$4+2+1=7$$$ хвилин.