AtCoder Beginner Contest 141 - Powerful Discount Tickets

Takahashi is going to buy N items one by one.
The price of the i-th item he buys is A_i yen (the currency of Japan).
He has M discount tickets, and he can use any number of them when buying an item.
If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.
What is the minimum amount of money required to buy all the items?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N, M \leq 10^5
 - 1 \leq A_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 A_2 ... A_N

-----Output-----
Print the minimum amount of money required to buy all the items.

-----Sample Input-----
3 3
2 13 8

-----Sample Output-----
9

We can buy all the items for 9 yen, as follows:
 - Buy the 1-st item for 2 yen without tickets.
 - Buy the 2-nd item for 3 yen with 2 tickets.
 - Buy the 3-rd item for 4 yen with 1 ticket.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
import heapq
(N, M) = map(int, input().split())
A = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(A)
for x in range(M):
	t = -1 * heapq.heappop(A)
	heapq.heappush(A, -1 * (t // 2))
print(-1 * sum(A))


import heapq
(n, m) = map(int, input().split())
a = list(map(lambda x: -1 * int(x), input().split()))
heapq.heapify(a)
for _ in range(m):
	heapq.heappush(a, -(-heapq.heappop(a) // 2))
print(-sum(a))


import heapq
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
	print(a[0] // 2 ** m)
	return
a = list(map(lambda x: x * -1, a))
heapq.heapify(a)
while m > 0:
	m -= 1
	i = heapq.heappop(a) * -1
	i //= 2
	heapq.heappush(a, i * -1)
print(sum(a) * -1)


def main():
	import heapq
	import sys
	pin = sys.stdin.readline
	pout = sys.stdout.write
	perr = sys.stderr.write
	(N, M) = map(int, pin().split())
	A = list(map(int, pin().split()))
	B = list(map(lambda x: -x, A))
	heapq.heapify(B)
	for i in range(M):
		t = heapq.heappop(B)
		s = -(-t // 2)
		heapq.heappush(B, s)
	ans = 0
	for j in range(N):
		q = heapq.heappop(B)
		ans += -q
	print(ans)
	return
main()


import heapq as hq
(n, m) = map(int, input().split())
a = [-int(x) for x in input().split()]
hq.heapify(a)
for i in range(m):
	x = hq.heappop(a)
	x = -x // 2
	hq.heappush(a, -x)
print(sum(a) * -1)


import heapq
(N, M) = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
heapq.heapify(A)
for _ in range(M):
	v = heapq.heappop(A)
	heapq.heappush(A, -(-v // 2))
print(-sum(A))


import heapq
from collections import deque
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
for i in range(n):
	A[i] *= -1
heapq.heapify(A)
for i in range(m):
	x = heapq.heappop(A)
	if x % 2 == 0:
		x //= 2
	else:
		x = x // 2 + 1
	heapq.heappush(A, x)
ans = -1 * sum(A)
print(ans)


import heapq
(n, m) = map(int, input().split())
A = [-n for n in map(int, input().split())]
heapq.heapify(A)
while m >= 1:
	k = -heapq.heappop(A) // 2
	heapq.heappush(A, -k)
	m -= 1
print(-sum(A))


import math
import heapq
(n, m) = map(int, input().split())
a = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(a)
for i in range(m):
	heapq.heappush(a, math.ceil(heapq.heappop(a) / 2))
print(int(-1 * sum(a)))


from heapq import heapify, heappop, heappush
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
q = []
for a in A:
	q.append((a // 2 - a, a, 1))
heapify(q)
ans = sum(A)
for _ in range(M):
	(discount, a, n) = heappop(q)
	ans += discount
	if ans == 0:
		break
	heappush(q, (a // 2 ** (n + 1) - a // 2 ** n, a, n + 1))
print(ans)


import math
import bisect
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for _ in range(M):
	x = math.floor(A.pop(N - 1) / 2)
	bisect.insort(A, x)
print(sum(A))


(n, m) = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
import heapq
heapq.heapify(A)
for i in range(m):
	a = heapq.heappop(A)
	heapq.heappush(A, -(-a // 2))
print(-sum(A))


import heapq as hq
(N, M) = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
hq.heapify(A)
for i in range(M):
	a = -hq.heappop(A)
	hq.heappush(A, -(a // 2))
print(-sum(A))


import heapq

def solve(n, m, a):
	a = [-x for x in a]
	heapq.heapify(a)
	for _ in range(m):
		x = heapq.heappop(a)
		heapq.heappush(a, -(abs(x) // 2))
	return abs(sum(a))

def main():
	(N, M) = list(map(int, input().split()))
	a = list(sorted(map(int, input().split())))
	print(solve(N, M, a))
	pass

def __starting_point():
	main()
__starting_point()


import heapq
(N, M) = [int(x) for x in input().split()]
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for i in range(M):
	x = heapq.heappop(A)
	x = -x // 2
	heapq.heappush(A, -x)
print(-sum(A))


import heapq
(N, M) = [int(_) for _ in input().split()]
A = [-int(_) for _ in input().split()]
heapq.heapify(A)
for _ in range(M):
	a = heapq.heappop(A)
	heapq.heappush(A, -(-a // 2))
print(-sum(A))


(n, m) = map(int, input().split())
A = [-int(a) for a in input().split()]
A = sorted(A)
from heapq import heappush, heappop
for _ in range(m):
	x = heappop(A)
	heappush(A, -(-x // 2))
print(-sum(A))


import heapq
(n, m) = list(map(int, input().split()))
l = sorted([int(a) * -1 for a in input().split()])
for i in range(m):
	high = heapq.heappop(l)
	heapq.heappush(l, -(-high // 2))
print(abs(sum(l)))


from heapq import *
(n, m, *a) = eval(',-'.join(open(0).read().split()))
a.sort()
exec('heappush(a,-~heappop(a)//2);' * -m)
print(-sum(a))


import heapq
(n, m) = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
heapq.heapify(a)
for i in range(m):
	heapq.heapreplace(a, a[0] / 2)
print(-sum(map(int, a)))


import heapq
(n, m) = (int(x) for x in input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for i in range(m):
	a = -1 * heapq.heappop(A)
	a //= 2
	heapq.heappush(A, -a)
print(-sum(A))


(N, M) = map(int, input().split())
(*A,) = map(int, input().split())
from heapq import *
B = []
for a in A:
	B.append(-a)
heapify(B)
for i in range(M):
	b = heappop(B)
	b = 0 - -b // 2
	heappush(B, b)
print(-sum(B))


import math
import heapq
(n, m) = map(int, input().split())
price = list(map(int, input().split()))
price = [-i for i in price]
heapq.heapify(price)
for i in range(m):
	sm = heapq.heappop(price)
	sm = -(-sm // 2)
	heapq.heappush(price, sm)
price = [-i for i in price]
print(sum(price))


import sys
input = sys.stdin.readline
import heapq
(n, m) = list(map(int, input().split()))
a = []
for i in input().split():
	heapq.heappush(a, -int(i))
for i in range(m):
	p = -heapq.heappop(a)
	p = p // 2
	heapq.heappush(a, -p)
print(-sum(a))


import heapq as hq
(N, M) = map(int, input().split())
A = [-x for x in map(int, input().split())]
hq.heapify(A)
for i in range(M):
	m = A[0]
	hq.heappushpop(A, -(-m // 2))
print(-sum(A))


import heapq
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A = [-i for i in A]
heapq.heapify(A)
for i in range(M):
	a = -heapq.heappop(A)
	heapq.heappush(A, -(a // 2))
print(-sum(A))


from heapq import heapify, heappop, heappush
(N, M) = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
heapify(A)
for i in range(M):
	heappush(A, -(-heappop(A) // 2))
print(-sum(A))


(N, M) = map(int, input().split())
(*A,) = map(int, input().split())
import heapq
B = sorted((-a for a in A))
heapq.heapify(B)
for _ in [0] * M:
	b = -(-heapq.heappop(B) // 2)
	heapq.heappush(B, b)
print(-sum(B))


import heapq
(n, m) = map(int, input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
	max = -heapq.heappop(a)
	heapq.heappush(a, -1 * (max // 2))
print(-sum(a))


from bisect import insort_right
(n, m, *a) = map(int, open(0).read().split())
a.sort()
for _ in range(m):
	insort_right(a, a.pop() >> 1)
print(sum(a))


import heapq
(N, M) = map(int, input().split())
L = [-int(i) for i in input().split()]
heapq.heapify(L)
for i in range(M):
	h = -(-heapq.heappop(L) // 2)
	heapq.heappush(L, h)
print(-sum(L))


from bisect import bisect_left as b
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
while m > 0:
	i = a.pop(-1) // 2
	a.insert(b(a, i), i)
	m -= 1
print(sum(a))


from heapq import *
(n, m) = map(int, input().split())
A = list(map(lambda x: int(x) * -1, input().split()))
heapify(A)
for _ in range(m):
	max_a = heappop(A) * -1
	max_a //= 2
	heappush(A, -max_a)
print(-sum(A))


from heapq import *
(n, m, *a) = map(lambda x: -int(x), open(0).read().split())
heapify(a)
for _ in [0] * -m:
	heappush(a, 0 - heappop(a) // -2)
print(-sum(a))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] *= -1
import heapq, math
heapq.heapify(a)
for _ in range(m):
	b = heapq.heappop(a) * -1
	b //= 2
	heapq.heappush(a, b * -1)
print(sum(a) * -1)


import heapq
(N, M) = list(map(int, input().split()))
h = []
for x in input().split():
	heapq.heappush(h, -int(x))
for i in range(M):
	x = -heapq.heappop(h)
	x //= 2
	heapq.heappush(h, -x)
print(-sum(h))


import heapq
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
q = []
for i in a:
	heapq.heappush(q, -i)
for _ in range(m):
	heapq.heappush(q, -(heapq.heappop(q) // -2))
print(-sum(q))


from heapq import *
(N, M) = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
heapify(a)
for _ in range(M):
	n = -heappop(a)
	n //= 2
	heappush(a, -n)
print(-sum(a))


f = lambda : input().split()
(_, m) = map(int, f())
l = [-int(i) for i in f()]
from heapq import *
heapify(l)
for _ in range(m):
	heappush(l, -(-heappop(l) // 2))
print(-sum(l))


from heapq import heapify, heapreplace
(n, m) = map(int, input().split())
L = [-i for i in map(int, input().split())]
heapify(L)
for _ in range(m):
	heapreplace(L, L[0] // 2 + L[0] % 2)
print(-sum(L))


3
import heapq

def main():
	line1 = input()
	line2 = input()
	(n, m) = list(map(int, line1.split()))
	l = list(map(int, line2.split()))
	ans = sum(l)
	for i in range(len(l)):
		l[i] *= -1
	heapq.heapify(l)
	for i in range(m):
		price = heapq.heappop(l) * -1
		new_price = price // 2
		heapq.heappush(l, new_price * -1)
		ans -= price - new_price
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


import re
import sys
import math
import itertools
import bisect
import heapq
from copy import copy
from collections import deque, Counter
from decimal import Decimal
import functools

def get_primenumber(number):
	prime_list = []
	search_list = list(range(2, number + 1))
	while search_list[0] <= math.sqrt(number):
		head_num = search_list.pop(0)
		prime_list.append(head_num)
		search_list = [num for num in search_list if num % head_num != 0]
	prime_list.extend(search_list)
	return prime_list

def factrization_prime(number):
	factor = {}
	div = 2
	s = math.sqrt(number)
	while div < s:
		div_cnt = 0
		while number % div == 0:
			div_cnt += 1
			number //= div
		if div_cnt != 0:
			factor[div] = div_cnt
		div += 1
	if number > 1:
		factor[number] = 1
	return factor

def v():
	return input()

def k():
	return int(input())

def S():
	return input().split()

def I():
	return list(map(int, input().split()))

def X():
	return list(input())

def L():
	return list(input().split())

def l():
	return list(map(int, input().split()))

def lcm(a, b):
	return a * b // math.gcd(a, b)
sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7
cnt = 0
ans = 0
num = []
inf = float('inf')
al = 'abcdefghijklmnopqrstuvwxyz'
AL = al.upper()
(n, m) = I()
A = l()
A = list([x * -1 for x in A])
heapq.heapify(A)
for i in range(m):
	mm = heapq.heappop(A)
	if mm % 2 != 0:
		heapq.heappush(A, mm // 2 + 1)
	else:
		heapq.heappush(A, mm // 2)
A = list([x * -1 for x in A])
print(sum(A))


import copy

def bi_search(money, M, N):
	money.sort()
	left = 0
	right = money[N - 1] + 1
	mid = 0
	while True:
		mid = int((left + right) / 2)
		cnt = 0
		money_tmp = copy.copy(money)
		for i in range(N):
			while True:
				if money_tmp[i] <= mid:
					break
				else:
					money_tmp[i] //= 2
					cnt += 1
		if cnt == M:
			return (mid, cnt)
		elif cnt < M:
			right = mid
			tmp = cnt
		elif cnt > M:
			left = mid + 1
		if left == right:
			return (right, tmp)

def main():
	(N, M) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	(max_money, cnt) = bi_search(A, M, N)
	cnt = M - cnt
	ans = 0
	for i in range(N):
		if max_money >= A[i]:
			continue
		else:
			while True:
				A[i] //= 2
				if max_money >= A[i]:
					break
	A.sort(reverse=True)
	j = 0
	if A[j] == 0:
		return 0
	for i in range(cnt):
		A[j] //= 2
		j += 1
	for i in range(N):
		ans += A[i]
	return ans
print(main())


from heapq import *
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
q = []
for x in a:
	heappush(q, -x)
for i in range(m):
	temp = -heappop(q)
	heappush(q, -(temp // 2))
print(-sum(q))


(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
import heapq
a = list([x * -1 for x in A])
heapq.heapify(a)
for i in range(K):
	num = heapq.heappop(a) * -1
	heapq.heappush(a, -1 * int(num / 2))
	if num == 0:
		break
print(-sum(a))


from heapq import *
(n, m, *a) = [-int(i) for i in open(0).read().split()]
heapify(a)
while m:
	heappush(a, 0 - -heappop(a) // 2)
	m += 1
print(-sum(a))


import heapq
(n, m) = map(int, input().split())
A = [int(i) * -1 for i in input().split()]
heapq.heapify(A)
for i in range(m):
	M = heapq.heappop(A)
	heapq.heappush(A, -(-M // 2))
ans = -sum(A)
print(ans)


import heapq
(n, m, *a) = list(map(int, open(0).read().split()))
a = list([-x for x in a])
heapq.heapify(a)
for i in range(m):
	b = -heapq.heappop(a)
	heapq.heappush(a, -(b >> 1))
print(-sum(a))


import heapq

class Heapq:

	def __init__(self, arr, desc=False):
		if desc:
			arr = [-a for a in arr]
		self.sign = -1 if desc else 1
		self.hq = arr
		heapq.heapify(self.hq)

	def pop(self):
		return heapq.heappop(self.hq) * self.sign

	def push(self, a):
		heapq.heappush(self.hq, a * self.sign)

	def top(self):
		return self.hq[0] * self.sign
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
q = Heapq(A, True)
for i in range(M):
	x = q.pop()
	q.push(x // 2)
print(sum([q.pop() for _ in range(N)]))


import heapq
import math
(N, M) = map(int, input().split())
h = []
for i in input().split():
	heapq.heappush(h, -int(i))
for i in range(M):
	t = heapq.heappop(h)
	heapq.heappush(h, math.ceil(t / 2))
print(-sum(h))


import heapq
(N, M) = map(int, input().split())
l = list(map(int, input().split()))
l = [-n for n in l]
heapq.heapify(l)
while M > 0:
	a = -heapq.heappop(l)
	a = a // 2
	heapq.heappush(l, -a)
	M -= 1
print(-sum(l))


import heapq
prio = []
(n, m) = list(map(int, input().split()))
nums = list(map(int, input().split()))
for num in nums:
	heapq.heappush(prio, -num)
for i in range(m):
	temp = heapq.heappop(prio)
	heapq.heappush(prio, -(-temp // 2))
print(-sum(prio))


import heapq as hp
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [-a for a in A]
hp.heapify(A)
for _ in range(M):
	x = hp.heappop(A)
	hp.heappush(A, x / 2)
A = [int(-a) for a in A]
print(sum(A))


import heapq
(N, M) = map(int, input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
	heapq.heapreplace(A, int(A[0] / 2))
print(-sum(A))


from heapq import heapify, heappush, heappop
(n, m) = list(map(int, input().split()))
A = list(map(int, input().split()))
A = list([x * -1 for x in A])
heapify(A)
for i in range(m):
	x = heappop(A)
	x = (x + 1) // 2
	heappush(A, x)
print(-1 * sum(A))


import heapq
(n, m) = map(int, input().split())
a = [-int(x) for x in input().split()]
heapq.heapify(a)
for i in range(m):
	t = heapq.heappop(a)
	t = -t // 2
	heapq.heappush(a, -t)
print(-sum(a))


import heapq
import math
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))

def __starting_point():
	a = [-1 * i for i in A]
	heapq.heapify(a)
	for _ in range(M):
		temp = heapq.heappop(a)
		heapq.heappush(a, math.ceil(temp / 2))
	ans = [-1 * i for i in a]
	print(sum(ans))
__starting_point()


import heapq
(n, m) = map(int, input().split())
a = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(a)
while m > 0:
	a_max = heapq.heappop(a)
	if a_max == 0:
		break
	heapq.heappush(a, -1 * (-a_max // 2))
	m -= 1
print(sum(a) * -1)


import heapq
(n, m) = map(int, input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)
for _ in range(m):
	tmp = heapq.heappop(a)
	heapq.heappush(a, -(-tmp // 2))
print(-sum(a))


import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10 ** 6)

def zz():
	return list(map(int, sys.stdin.readline().split()))

def z():
	return int(sys.stdin.readline())

def S():
	return sys.stdin.readline()[:-1]

def C(line):
	return [sys.stdin.readline() for _ in range(line)]
(N, M) = zz()
A = zz()
A = [-a for a in A]
heapq.heapify(A)
for i in range(M):
	money = heapq.heappop(A)
	money *= -1
	money //= 2
	money *= -1
	heapq.heappush(A, money)
print(sum(A) * -1)


import heapq
(n, m) = map(int, input().split())
a = [-int(x) for x in input().split()]
heapq.heapify(a)
for _ in range(m):
	cur = heapq.heappop(a)
	heapq.heappush(a, -(-cur // 2))
print(-sum(a))


import bisect
(n, m) = map(int, input().split())
a = sorted(list(map(int, input().split())))
for i in range(m):
	t = a[-1]
	t //= 2
	a.pop()
	bisect.insort_left(a, t)
print(sum(a))


def main():
	from heapq import heapify, heappush, heappop
	(n, m, *a) = [-int(i) for i in open(0).read().split()]
	heapify(a)
	for _ in range(-m):
		heappush(a, 0 - -heappop(a) // 2)
	print(-sum(a))
main()


import sys
import heapq
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
a_list = list(map(int, input().split()))
a_list = list([x * -1 for x in a_list])
heapq.heapify(a_list)
while m > 0:
	max_a = heapq.heappop(a_list)
	heapq.heappush(a_list, -1 * (-max_a // 2))
	m -= 1
print(-sum(a_list))


import math

class Heap:

	def __init__(self, array):
		self.array = list(array)
		self._build_heap()

	def _build_heap(self):
		for i in reversed(range(len(self.array) // 2)):
			self._min_heap(i)

	def _min_heap(self, i):
		left = 2 * (i + 1) - 1
		right = 2 * (i + 1) + 1 - 1
		length = len(self.array) - 1
		smallest = i
		if left <= length and self.array[i] > self.array[left]:
			smallest = left
		if right <= length and self.array[smallest] > self.array[right]:
			smallest = right
		if smallest != i:
			(self.array[i], self.array[smallest]) = (self.array[smallest], self.array[i])
			self._min_heap(smallest)

	def pop(self):
		tmp = self.array[0]
		self.array[0] = self.array[-1]
		del self.array[-1]
		self._min_heap(0)
		return tmp

	def push(self, v):
		self.array.append(v)
		index = len(self.array)
		while self.array[index // 2 - 1] > self.array[index - 1]:
			(self.array[index // 2 - 1], self.array[index - 1]) = (self.array[index - 1], self.array[index // 2 - 1])
			index = index // 2
(n, m) = map(int, input().split())
a = map(lambda x: int(x) * -1, input().split())
a = Heap(a)
for i in range(m):
	a.push(math.ceil(a.pop() / 2))
print(int(-1 * sum(a.array)))


import sys
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)
from heapq import heapify, heappop, heappush

def Main():
	(n, m) = read_ints()
	a = read_int_list()
	a = [-x for x in a]
	heapify(a)
	while m:
		cost = heappop(a)
		if cost == 0:
			break
		heappush(a, -(-cost // 2))
		m -= 1
	print(-sum(a))

def __starting_point():
	Main()
__starting_point()


import heapq
(N, M) = map(int, input().split())
A = [-int(x) for x in input().split()]
A.sort()
for i in range(M):
	rem = A[0]
	heapq.heappush(A, int(rem / 2))
	heapq.heappop(A)
print(-sum(A))


import heapq
(N, M) = list(map(int, input().split()))
A = list([int(x) * -1 for x in input().split()])
heapq.heapify(A)
for i in range(M):
	max_num = heapq.heappop(A) * -1
	heapq.heappush(A, -1 * (max_num // 2))
A = [x * -1 for x in A]
print(sum(A))


import heapq
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
hq = []
for i in A:
	heapq.heappush(hq, -i)
for _ in range(m):
	m = -(-heapq.heappop(hq) // 2)
	heapq.heappush(hq, m)
print(-sum(hq))


import heapq
(N, M) = map(int, input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for _ in range(M):
	tmin = heapq.heappop(A)
	heapq.heappush(A, -1 * (-tmin // 2))
print(-sum(A))


import heapq
(N, M) = map(int, input().split())
a = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(a)
for _ in range(M):
	tmp = heapq.heappop(a)
	heapq.heappush(a, int(tmp / 2))
print(-sum(a))


import heapq
(N, M) = map(int, input().split())
A = [-int(a) for a in input().split()]
assert len(A) == N
heapq.heapify(A)
for m in range(M):
	heapq.heapreplace(A, -(-A[0] // 2))
print(-sum(A))


from heapq import heappop, heappush, heapify
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
arr = [-x for x in arr]
heapify(arr)
for _ in range(m):
	a = heappop(arr)
	heappush(arr, -(-a // 2))
print(-sum(arr))


import heapq
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x * -1, a))
heapq.heapify(a)
for i in range(m):
	tmp = heapq.heappop(a)
	tmp /= 2
	heapq.heappush(a, tmp)
ans = 0
for aa in a:
	ans += aa // -1
print(int(ans))


import heapq
(N, M) = map(int, input().split())
lsA = list(map(int, input().split()))
lsA = [-i for i in lsA]
heapq.heapify(lsA)
for i in range(M):
	maxA = heapq.heappop(lsA)
	heapq.heappush(lsA, -(-maxA // 2))
lsA = [-i for i in lsA]
print(sum(lsA))


from heapq import *
from math import *
(n, m, *a) = map(int, open(0).read().split())
a = [-i for i in a]
heapify(a)
for i in range(m):
	heappush(a, -(-heappop(a) // 2))
print(-sum(a))


(n, m) = [int(j) for j in input().split()]
a = [-int(j) for j in input().split()]
import heapq
heapq.heapify(a)
for i in range(m):
	p = heapq.heappop(a)
	p = -p // 2
	heapq.heappush(a, -p)
print(-sum(a))


import heapq
(N, M) = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
heapq.heapify(A)
for m in range(M):
	a = -heapq.heappop(A)
	heapq.heappush(A, -(a // 2))
print(-sum(A))


def main():
	(N, M) = [int(x) for x in input().split(' ')]
	A = [int(a) for a in input().split(' ')]
	D = []
	for i in range(len(A)):
		tmp = A[i]
		while tmp > 0:
			half = int(tmp / 2)
			D.append(tmp - half)
			tmp = half
	D.sort(reverse=True)
	print(sum(A) - sum(D[:M]))
main()


import heapq as hq
(n, m) = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
hq.heapify(a)
for i in range(m):
	v = -hq.heappop(a)
	hq.heappush(a, -(v // 2))
print(-sum(a))


import heapq
from math import ceil
(n, m) = map(int, input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
	heapq.heappush(a, ceil(heapq.heappop(a) / 2))
print(-sum(a))


import heapq
(N, M) = map(int, input().split())
A = [int(_) * -1 for _ in input().split()]
heapq.heapify(A)
while M != 0:
	max_ = -heapq.heappop(A) // 2
	heapq.heappush(A, -max_)
	M -= 1
print(-sum(A))


from heapq import *
(n, m, *a) = eval(',-'.join(open(0).read().split()))
x = 0
a.sort()
exec('x=heappushpop(a,-~x//2);' * -~-m)
print(-x - sum(a))


class Heap:

	def __init__(self, x: list):
		self.heap = []
		for item in x:
			self.push(item)

	def push(self, item: int):
		self.heap.append(item)
		idx_child = len(self.heap) - 1
		while idx_child > 0:
			idx_parent = (idx_child - 1) // 2
			if self.heap[idx_parent] <= item:
				break
			tmp = self.heap[idx_child]
			(self.heap[idx_parent], self.heap[idx_child]) = (self.heap[idx_child], self.heap[idx_parent])
			idx_child = idx_parent

	def pop(self) -> int:
		ret = self.heap[0]
		self.heap[0] = self.heap[-1]
		self.heap.pop()
		idx_parent = 0
		while idx_parent * 2 + 1 < len(self.heap):
			(idx_child_l, idx_child_r) = (2 * idx_parent + 1, 2 * idx_parent + 2)
			if idx_child_r < len(self.heap) and self.heap[idx_child_r] < self.heap[idx_child_l]:
				idx_child = idx_child_r
			else:
				idx_child = idx_child_l
			if self.heap[idx_parent] <= self.heap[idx_child]:
				break
			(self.heap[idx_child], self.heap[idx_parent]) = (self.heap[idx_parent], self.heap[idx_child])
			idx_parent = idx_child
		return ret

	def load(self) -> list:
		return self.heap
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [-a for a in A]
heap = Heap(A)
for _ in range(M):
	x = heap.pop()
	heap.push(x / 2)
A = heap.load()
A = [int(-a) for a in A]
print(sum(A))


(N, M) = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
import heapq
heapq.heapify(A)
for _ in range(M):
	heapq.heapreplace(A, -(-A[0] // 2))
print(-sum(A))


import sys
import math
import itertools
import collections
from collections import deque
import heapq
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().strip()
NI = lambda : int(input())
NMI = lambda : map(int, input().split())
NLI = lambda : list(NMI())
SI = lambda : input()

def main():
	(N, M) = NMI()
	A = NLI()
	A = list(map(lambda x: x * -1, A))
	heapq.heapify(A)
	for m in range(M):
		highest = heapq.heappop(A) * -1
		discounted = math.floor(highest / 2) * -1
		heapq.heappush(A, discounted)
	print(sum(A) * -1)

def __starting_point():
	main()
__starting_point()


import heapq
(n, m) = map(int, input().split())
hp = map(lambda x: -1 * int(x), input().split())
hp = list(hp)
heapq.heapify(hp)
for i in range(m):
	item = -1 * heapq.heappop(hp)
	item = item // 2
	heapq.heappush(hp, -item)
print(-1 * sum(hp))


import heapq
(n, m, *a) = map(int, open(0).read().split())
a = list(map(lambda x: x * -1, a))
heapq.heapify(a)
for _ in range(m):
	heapq.heappush(a, -(-heapq.heappop(a) // 2))
print(-sum(a))


import heapq
import sys
lines = sys.stdin.readlines()
(N, M) = [int(n) for n in lines[0].strip().split()]
prices = [-int(n) for n in lines[1].strip().split()]
heapq.heapify(prices)
for _ in range(M):
	price = -heapq.heappop(prices)
	heapq.heappush(prices, -1 * (price // 2))
print(-sum(prices))


import heapq
(N, M) = list(map(int, input().split()))
hq = []
for price in map(int, input().split()):
	heapq.heappush(hq, -price)
for i in range(M):
	p = -heapq.heappop(hq)
	p /= 2
	heapq.heappush(hq, -p)
result = -sum([int(p) for p in hq])
print(result)


from heapq import *
(n, m, *a) = [-int(i) for i in open(0).read().split()]
a.sort()
exec('heappush(a,-~heappop(a)//2);' * -m)
print(-sum(a))


from heapq import *
(n, m) = map(int, input().split())
h = []
for a in input().split():
	heappush(h, int(a) * -1)
for i in range(m):
	a = heappop(h)
	heappush(h, -(-a // 2))
print(abs(sum(h)))


(n, m) = map(int, input().split())
a = [-int(aa) for aa in input().split()]
import heapq
heapq.heapify(a)
for _ in range(m):
	now = -heapq.heappop(a)
	heapq.heappush(a, -(now // 2))
print(-sum(a))


from heapq import heappop, heappush
(n, m) = map(int, input().split())
aa = list(map(int, input().split()))
a = []
for i in range(n):
	heappush(a, -aa[i])
for _ in range(m):
	heappush(a, (heappop(a) + 1) // 2)
print(-sum(a))


from collections import deque
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
queue_A = deque(A)
queue_B = deque()
for i in range(M):
	if len(queue_B) > 0 and queue_B[0] >= queue_A[0]:
		queue_A.appendleft(queue_B.popleft())
	queue_A[0] //= 2
	if len(queue_A) > 1 and queue_A[0] < queue_A[1]:
		queue_B.append(queue_A.popleft())
print(sum(queue_A) + sum(queue_B))


from heapq import heapify, heappush, heappop

def main():
	(N, M) = list(map(int, input().split()))
	A = [-x for x in map(int, input().split())]
	heapify(A)
	for i in range(M):
		tmp = -heappop(A)
		tmp2 = tmp // 2
		heappush(A, -tmp2)
	ans = 0
	for i in range(N):
		ans += A[i]
	ans = abs(ans)
	return ans
print(main())


import sys
import re
import queue
import collections
import math
from decimal import *
from copy import deepcopy
from collections import Counter, deque
import heapq
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from typing import Callable
from decimal import Decimal, getcontext

def i_input():
	return int(input())

def i_map():
	return map(int, input().split())

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def lcm(a, b):
	return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
	(N, M) = i_map()
	A = i_list()
	for i in range(0, len(A)):
		A[i] = -A[i]
	heapq.heapify(A)
	for i in range(0, M):
		tmp = math.ceil(heapq.heappop(A) / 2)
		heapq.heappush(A, tmp)
	sum = 0
	for i in range(0, len(A)):
		sum += -heapq.heappop(A)
	print(sum)

def __starting_point():
	main()
__starting_point()


import heapq
(N, M) = map(int, input().split())
A = list(map(lambda o: -int(o), input().split()))
heapq.heapify(A)
for i in range(0, M, 1):
	heapq.heappush(A, -(-heapq.heappop(A) >> 1))
print(-sum(A))


import heapq
(N, M) = map(int, input().split())
H = []
for i in input().split():
	heapq.heappush(H, -int(i))
for i in range(M):
	a = heapq.heappop(H)
	heapq.heappush(H, -(-a // 2))
print(-sum(H))


import heapq
(n, m) = map(int, input().split())
a = [int(x) * -1 for x in input().split()]
a = sorted(a)
for i in range(m):
	off = -1 * heapq.heappop(a) // 2
	heapq.heappush(a, -1 * off)
print(-1 * sum(a))


import heapq
(N, M) = list(map(int, input().split()))
A = list([-int(x) for x in input().split()])
heapq.heapify(A)
ans = 0
for i in range(M):
	most_expensive = -heapq.heappop(A)
	most_expensive //= 2
	heapq.heappush(A, -most_expensive)
print(-sum(A))


from heapq import *
(N, M, *A) = map(lambda x: -int(x), open(0).read().split())
heapify(A)
for _ in range(-M):
	heappush(A, 0 - heappop(A) // -2)
print(-sum(A))


import heapq
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
H = []
for a in A:
	heapq.heappush(H, -a)
for i in range(m):
	heapq.heappush(H, -(-heapq.heappop(H) // 2))
print(-sum(H))


f = lambda : map(int, input().split())
(_, m) = f()
l = list(map(lambda x: -x, f()))
import heapq as hq
hq.heapify(l)
for i in range(m):
	p = -hq.heappop(l) // 2
	hq.heappush(l, -p)
print(-sum(l))


(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
count = 0
while count != M:
	A[0] //= 2
	count += 1
	tmp = A[0]
	for i in range(1, N):
		if count == M:
			break
		if A[i] > tmp:
			A[i] //= 2
			count += 1
	A.sort(reverse=True)
ans = sum(A)
print(ans)


from heapq import heapify, heappush, heappop
(N, M, *A) = map(int, open(0).read().split())
Q = [-a for a in A]
heapify(Q)
for _ in range(M):
	a = heappop(Q)
	heappush(Q, -(-a // 2))
print(-sum(Q))


from heapq import *
(n, m, *a) = eval(',-'.join(open(0).read().split()))
a.sort()
for _ in [0] * -m:
	heappush(a, 0 - -heappop(a) // 2)
print(-sum(a))


import heapq
(n, m) = map(int, input().split())
a = [-int(x) for x in input().split()]
heapq.heapify(a)
for _ in range(m):
	t = -(-a[0] // 2)
	heapq.heapreplace(a, t)
print(-sum(a))


from heapq import *
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
heap = []
for i in a:
	heappush(heap, -i)
for _ in range(m):
	tmp = heappop(heap)
	heappush(heap, -(-tmp // 2))
ans = 0
for a in heap:
	ans += -a
print(ans)


import bisect
(N, M) = map(int, input().split())
A = sorted(map(int, input().split()))
for i in range(M):
	bisect.insort(A, A.pop() // 2)
print(sum(A))


import heapq
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
ls = []
for item in A:
	heapq.heappush(ls, -item)
for m in range(M):
	tmp = -heapq.heappop(ls)
	tmp = tmp // 2
	heapq.heappush(ls, -tmp)
print(-sum(ls))


import heapq
(n, m) = list(map(int, input().split()))
cost = list(map(int, input().split()))
cost = list([x * -1 for x in cost])
heapq.heapify(cost)
while m != 0:
	max = heapq.heappop(cost)
	val = -1 * max // 2 * -1
	m -= 1
	heapq.heappush(cost, val)
cost = list([x * -1 for x in cost])
print(sum(cost))


import heapq
(n, m) = map(int, input().split())
a = list(map(lambda s: -int(s), input().split()))
heapq.heapify(a)
for i in range(m):
	heapq.heappush(a, (heapq.heappop(a) + 1) // 2)
print(-sum(a))


import sys
stdin = sys.stdin
(n, m) = map(int, stdin.readline().split())
an = [i * -1 for i in map(int, stdin.readline().split())]
import heapq
heapq.heapify(an)
for _ in range(m):
	b = heapq.heappop(an)
	heapq.heappush(an, -1 * (-1 * b // 2))
ans = -1 * sum(an)
print(ans)


import heapq
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [A[i] * -1 for i in range(N)]
heapq.heapify(A)
for i in range(M):
	q = heapq.heappop(A)
	if q == 0:
		print(0)
		return
	heapq.heappush(A, int(q / 2))
print(sum(A) * -1)


import heapq
(N, M) = map(int, input().split())
arr = list(map(int, input().split()))
hq = []
for i in arr:
	heapq.heappush(hq, -i)
while M > 0:
	a = heapq.heappop(hq)
	heapq.heappush(hq, a / 2)
	M -= 1
ans = 0
for i in hq:
	ans += int(-i)
print(ans)


import heapq
(n, m) = map(int, input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
	k = heapq.heappop(a)
	heapq.heappush(a, -(abs(k) // 2))
print(-sum(a))


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
import bisect
for i in range(M):
	bisect.insort(A, A[-1] / 2)
	A.pop(-1)
for i in range(N):
	A[i] = int(A[i])
print(sum(A))


import heapq
(n, m) = map(int, input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)
for _ in range(m):
	heapq.heappushpop(a, -(-a[0] // 2))
print(-sum(a))


import heapq
(N, M) = list(map(int, input().split()))
A = list([-int(x) for x in input().split()])
heapq.heapify(A)
for _ in range(M):
	p = -heapq.heappop(A)
	tmp = p // 2
	heapq.heappush(A, -tmp)
print(-sum(A))


import sys

def input():
	return sys.stdin.readline().rstrip()
import heapq
(N, M) = list(map(int, input().split()))
A = list([int(x) * -1 for x in input().split()])
heapq.heapify(A)
for i in range(M):
	a = heapq.heappop(A)
	a *= -1
	a //= 2
	a *= -1
	heapq.heappush(A, a)
print(-sum(A))


from heapq import *
(N, M) = map(int, input().split())
A = []
for a in map(int, input().split()):
	heappush(A, -a)
for _ in range(M):
	x = -heappop(A)
	x //= 2
	heappush(A, -x)
print(-sum(A))


from bisect import bisect
(N, M) = map(int, input().split())
Ali = list(map(int, input().split()))
Ali.sort()
for i in range(M):
	a = Ali.pop(-1)
	a //= 2
	Ali.insert(bisect(Ali, a), a)
print(sum(Ali))


import heapq
(N, M) = map(int, input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
	a = -heapq.heappop(A) >> 1
	heapq.heappush(A, -a)
print(-sum(A))


from heapq import *
(n, m, *a) = map(lambda x: -int(x), open(0).read().split())
heapify(a)
exec('heappush(a,0-heappop(a)//-2);' * -m)
print(-sum(a))


import heapq
(N, M) = map(int, input().split())
A = [-int(n) for n in input().split()]
heapq.heapify(A)
for x in range(M):
	heapq.heappush(A, heapq.heappop(A) / 2)
A_int = map(int, A)
print(-sum(A_int))


import heapq
(N, M) = map(int, input().split())
A_list = list(map(int, input().split()))
A_list_minus = list(map(lambda x: x * -1, A_list))
heapq.heapify(A_list_minus)
for i in range(M):
	tmp_max = heapq.heappop(A_list_minus) * -1
	heapq.heappush(A_list_minus, -1 * (tmp_max // 2))
print(-1 * sum(A_list_minus))


import heapq
(N, M) = map(int, input().split())
a = [-int(x) for x in input().split()]
heapq.heapify(a)
for _ in range(M):
	b = heapq.heappop(a)
	heapq.heappush(a, -(-b // 2))
print(-sum(a))


from heapq import *
(n, m) = map(int, input().split())
q = []
[heappush(q, -int(i)) for i in input().split()]
for i in range(m):
	heappush(q, -(-heappop(q) // 2))
print(-sum(q))