4. Лука и массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Луки есть массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. К каждому элементу массива можно произвольное количество раз применять каждую из следующих магических операций:

  1. Выбрать некоторый элемент массива $$$a_i$$$ и заменить его на число $$$\left\lfloor \frac{a_i}{2} \right\rfloor$$$ (данная запись обозначает число $$$\frac{a_i}{2}$$$, округленное вниз). Для выполнения данной операции требуется $$$k$$$ единиц энергии.
  2. Выбрать некоторый элемент массива $$$a_i$$$ и заменить его на число $$$a_i - 1$$$. Для выполнения данной операции требуется одна единица энергии.

Ваша задача — определить, какое минимальное количество энергии необходимо, чтобы после выполнения магических операций все элементы массива принимли значение, равное единице (то есть, $$$a_1 = a_2 = \ldots = a_n = 1$$$).

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^4$$$) — количество элементов массива.

Вторая строка содержит одно целое число $$$k$$$ ($$$1 \le k \le 10^5$$$) — количество энергии, необходимое для выполнения операции первого типа.

Каждая из следующих $$$n$$$ строк содержит одно целое число $$$a_i$$$ ($$$1 \le a_i \le 10^{9}$$$) — элементы массива.

Обратите внимание, что ответ может быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.

Выходные данные

Выведите одно целое число — минимальное количество энергии, необходимое для требуемого преобразования массива.

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

Решения, правильно работающие только для случаев, когда $$$k = 1$$$, будут оцениваться в $$$25$$$ баллов.

Решения, правильно работающие только для случаев, когда все $$$a_i$$$ не превосходят $$$10^5$$$, будут оцениваться в $$$50$$$ баллов.

Примеры
Входные данные
3
1
4
1
3
Выходные данные
3
Входные данные
1
100
10
Выходные данные
9
Примечание

Рассмотрим первый пример из условия.

  1. Первый элемент массива равен $$$4$$$.Использовав одну единицу энергии, применим к нему первую магическую операцию, после чего первый элемент массива станет равен $$$\left\lfloor \frac{4}{2} \right\rfloor = 2$$$. После этого применим к нему вторую операцию, также затратив одну единицу энергии.
  2. Второй элемент массива уже равен $$$1$$$, поэтому применять к нему операции не нужно.
  3. К третьему элементу применим первую операцию, используя одну единицу энергии. После этого третий элемент станет равен $$$\left\lfloor \frac{3}{2} \right\rfloor = 1$$$.

Во втором примере из условия применение первой операции расходует слишком много единиц энергии, поэтому выгодно применить вторую операцию девять раз.