Скидочные купоны

На все товары в магазинах действуют скидки по случаю Дня дураков 15 мая. Таким образом, вы можете купить товар на сумму $X$ манатов за $\lfloor \frac{X}{2^Y}\rfloor$ манатов, предъявив $Y$ купонов на скидку. У вас есть $M$ купонов на скидку, и вы хотите купить $N$ товаров. Вы также знаете цену каждого товара $A_1$, $A_2$, ... , $A_N$ . Какова минимальная сумма денег, необходимая для покупки всех товаров?

Примечание: Здесь ⌊$X$⌋, означает целую часть числа $Х$ .

Input

В первой строке даётся два целых числа – $N$ и $M$ ($1\le N,M\le 10^5$) , во второй строке даётся $N$ целых – $A_1,A_2,...,A_N$ ($1\le A_i\le 10^9$) .

Output

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

Examples

Note

В первом примере все товары на $10$ манатов можно приобрести следующим образом: Первый товар $3$ маната без предъявления купона на скидку. Второй предмет можно получить, использовав $2$ купона на скидку $\lfloor \frac{15}{2^2}\rfloor$ = $3$ маната, а третий предмет, предъявив $1$ купон на скидку за $4$ маната. В итоге получилось: $3+3+4=10$.

Во втором примере используя $1000$ купонов на скидку, вы можете купить товар на $1000000$ манатов за $0$ манатов.

Scoring

Данная задача как указано внизу состоит из $5$ подзадач: