Степан збирається купувати \(N\) подарунків один за другим.

Ціна \(i\)-го товару, який він купує, — \(A_i\) гривень. У нього є \(M\) пільгових сертифікатів і він може використовувати будь-яку їх кількість при покупці товарів.

Якщо при покупці товару за ціною \(X\) гривень використовуються \(Y\) сертифікатів, то він може отримати цей товар за \(\frac{X}{2^Y}\) (округлено до найближчого цілого числа) гривень.

Яка мінімальна сума грошей потрібна, щоб купити всі предмети?

Формат вхідних даних

Перший рядок вхідного потоку містить цілі числа \(N< M\) (\(1 \le N,M \le 10^5\)).

Другий рядок містить \(N\) цілих чисел \(A_i\) (\(1 \le A_i \le 10^9\)), які розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести мінімальну суму грошей для купівлі подарунків.

Примітка

До прикладу 1:

Можна купити всі товари за 9 гривень, а саме:

• Купуйте 1-й товар за 2 грн.

• Купуйте 2-й товар за 3 грн з 2 сертифікатами.

• Купуйте 3-й товар за 4 грн з 1 сертифікатом.

Приклад вхідних даних

3 3
2 13 8

Приклад вихідних даних

9

Приклад вхідних даних

4 4
1 9 3 5

Приклад вихідних даних

6

Приклад вхідних даних

1 100000
1000000000

Приклад вихідних даних

0