410524: GYM104034 4 Лука и массив

У Луки есть массив из $$$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$$$.

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