Problem:
 Score : 400 points    Problem Statement 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 1 3 3
2 13 8      Sample Output 1 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.        Sample Input 2 4 4
1 9 3 5      Sample Output 2 6       Sample Input 3 1 100000
1000000000      Sample Output 3 0  We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.       Sample Input 4 10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 4 9500000000

Solution (Python):
import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
q=[]
for i in range(n):
  q.append((-1)*a[i])
heapq.heapify(q)
for k in range(m):
  ma=heapq.heappop(q)
  if ma%2==0:
    heapq.heappush(q,ma//2)
  else:
    heapq.heappush(q,ma//2+1)
print(sum(q)*(-1))

Solution (Python):
import sys
from heapq import *
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n,m=map(int, input().split())
    aa=list(map(int, input().split()))
    hp=[]
    for a in aa:
        heappush(hp,-a)
    for _ in range(m):
        a=heappop(hp)
        a/=2
        heappush(hp,a)
    print(sum(int(-a) for a in hp))

main()

Solution (Python):
import heapq
N,M = map(int,input().split())
Alist = map(int,input().split())
heapAlist = []

for A in Alist:
    heapq.heappush(heapAlist,-1*A)

for i in range(M):
    A = heapq.heappop(heapAlist)
    
    heapq.heappush(heapAlist,((-1)*A//2)*(-1))
    
print((-1)*sum(heapAlist))

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

Solution (Python):
import heapq
n,m = map(int,input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i]*=-1
h = a[0: n]
heapq.heapify(h)
for i in range(m):
    L=heapq.heappop(h)
    heapq.heappush(h,(L+1)//2)
print(sum(h)*(-1))

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

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

        heapq.heappush(A,-a)

    print(-sum(A))
if __name__ == '__main__':
    main()

Solution (Python):

import sys
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


def solve():
    N, M = list(map(int, sys.stdin.readline().split()))
    As = list(map(int, sys.stdin.readline().split()))
    h = Heapq([], True)
    for i, a in enumerate(As):
        h.push(a)

    for i in range(M):
        a = h.pop()//2
        h.push(a)

    ans = 0
    for i in range(N):
        ans += h.pop()

    print(ans)



if __name__ == "__main__":
    solve()

Solution (Python):
import heapq
A =[]
n,m= map(int,input().split())
a = list(map(int,input().split( )))
for i in range(n):
    a [i]*= -1
    heapq.heappush(A,a[i])

cnt = 0
while cnt < m:
    i = heapq.heappop(A)
    i *= -1
    i //=2
    i *=-1
    heapq.heappush(A,i)
    cnt+=1
sm = 0
for i in A:
    sm += i
sm *=-1

print(sm)

Solution (Python):
import heapq

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

print(-sum(ls))

Solution (Python):
import numpy as np
import heapq
n, m = map(int, input().split())
a = np.array(list(map(int, input().split())))
q = list(-a)
heapq.heapify(q)

for _ in range(m):
    temp = heapq.heappop(q)
    temp = -temp
    temp //= 2
    heapq.heappush(q, -temp)
print(-sum(q))

Solution (Python):
n,m = map(int,input().split())
item = list(map(int,input().split()))

item.sort(reverse=True)
s = 0

while s == 0:
    for i in range(n):
        if i == 0:
            item[i] = int(item[i]/2)
            m -= 1
            temp = item[i]
            if m == 0:
                s = 1
                break
            continue
        if item[i] > temp:
            item[i] = int(item[i]/2)
            m -= 1
            if m == 0:
                s = 1
                break
            continue
        item.sort(reverse=True)
        break
        

print(sum(item))

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))

from heapq import heappush, heappop

queue = []
for x in a:
    heappush(queue, -x)

for i in range(m):
    d = -heappop(queue)
    dd = d // 2
    heappush(queue, -dd)

print(int(-sum(queue)))

Solution (Python):
import sys
from heapq import heappush, heappop, heapify

input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(i)*-1 for i in input().split()]
heapify(A)

for _ in range(M):
    tmp = heappop(A)*-1
    heappush(A, tmp//2*-1)


print(sum(A)*-1)

Solution (Python):
from math import ceil
import heapq

N, M = map(int, input().split())
tmpA = list(map(int, input().split()))
A = [-a for a in tmpA]
heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, ceil(a / 2))

print(-sum(A))

Solution (Python):
import heapq
def double(x):
    return int(x) * -1
n, m = map(int, input().split())
A = list(map(double, input().split()))

heapq.heapify(A)

for i in range(m):
  te = heapq.heappop(A)
  heapq.heappush(A,(te*-1//2)*-1)
  
print(sum(A)*-1)

Solution (Python):
import heapq
import math

n,m = map(int,input().split())
a = list(map(int,input().split()))

b = []
for ai in a:
    heapq.heappush(b, ai* -1)


for i in range(m):
    tmp = math.ceil(heapq.heappop(b)/2)
    heapq.heappush(b, tmp)
    

print(sum(b) * -1)

Solution (Python):
n,m=map(int,input().split())
A=[int(i) for i in input().split()]

A.sort()
A.reverse()

if n==1:
    ans=A[0]//(2**m)
    print(ans)
else:
    A.append(0)
    big=A[0]
    stc=0
    now=0
    while m>0:
        A[now]=A[now]//2
        m-=1
        big=A[0]
        for i in range(n-1):
            if A[i+1]>=big and m>0:
                A[i+1]=A[i+1]//2
                m-=1
            else:
                A.sort()
                A.reverse()
                break
        
    else:
        print(sum(A))

Solution (Python):
import numpy as np
import heapq
n, maisuu = map(int, input().split())
a_map = map(int, input().split())
a_list = []
for a in a_map:
    heapq.heappush(a_list, -a)

for _ in range(maisuu):
    value = heapq.heappop(a_list)
    waribiki_value = int(value * 0.5)
    heapq.heappush(a_list, waribiki_value)
minus_sum = 0
for a in a_list:
    minus_sum += a
print(-minus_sum)

Solution (Python):
from heapq import  heapify,heappop,heappush

n,m = map(int,input().split())
A = list(map(int,input().split()))
A = [a*-1 for a in A]

heapify(A)
for i in range(m):
    a = heappop(A)
    if a % 2 == 0:
        a //= 2
    else:
        a = a // 2 +1
    heappush(A,a)

print(sum(A)*-1)

Solution (Python):
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: -x, A))

heapq.heapify(A)


for i in range(M):
    n = - (-heapq.heappop(A) // 2)
    heapq.heappush(A, n)

ans = - sum(A)
print(ans)

Solution (Python):
import heapq
n, m = map(int, input().split())
A = list(map(int, input().split()))
for i in range(n):
  A[i] = -A[i]
B = heapq.heapify(A)
i = 0
while i < m:
  h = heapq.heappop(A) 
  heapq.heappush(A, -(-h//2))
  i += 1
print(-sum(a for a in list(A)))

Solution (Python):
import heapq
N,M = map(int,input().split())
h=[]
li = input().split()
for i in li:
    heapq.heappush(h, -int(i))

for i in range(M):
    z = heapq.heappop(h) / 2
    heapq.heappush(h, z)
c=0
for i in h:
    c += int(i)
print(-c)

Solution (Python):
import heapq

N, M = map(int, input().split())
A = [-int(n) for n in input().split()]
heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    a = a // 2 if a % 2 == 0 else a // 2 + 1
    heapq.heappush(A, a)

print(-sum(A))

Solution (Python):
import heapq

def main():
    N, M = map(int,input().split())
    A = list(map(int,input().split()))

    H = []
    for a in A:
        H.append(-a)
    heapq.heapify(H)

    for _ in range(M):
        a = heapq.heappop(H)
        a = -1 * a
        a //= 2
        heapq.heappush(H,-a)

    print(-sum(H))
if __name__ == '__main__':
    main()

Solution (Python):
import heapq

import math
import numpy as np



N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = list(np.array(A) * -1)

heapq.heapify(A)

for i in range(M) :
    v = heapq.heappop(A)
    v = math.floor(-1 * v / 2) * -1
    heapq.heappush(A, v)

print(sum(A) * -1)

Solution (Python):
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    AS = list(map(lambda x: -int(x), input().split()))
    heapify(AS)
    for _ in range(M):
        a = heappop(AS)
        a = -(-a//2)
        heappush(AS,a)
    print(-sum(AS))

if __name__ == '__main__':
    main()

Solution (Python):
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


def main():
    N, M = map(int, input().split())
    an = list(map(int, input().split()))

    q = Heapq(an, True)

    for _ in range(M):
        value = q.pop() / 2.0
        q.push(value)

    res = sum(list(map(lambda x: int(x * -1), q.hq)))

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq as hq

N, M = map(int, input().split())
A = [-a for a in list(map(int, input().split()))]
hq.heapify(A)

for _ in range(M):
    target = hq.heappop(A)
    hq.heappush(A, -(-target//2))

print(-sum(A))

Solution (Python):
import heapq
import math

def minus_float(s):
    return float(s)*-1

def main():
    N,M=map(int, input().split())
    A=list(map(minus_float, input().split()))
    heapq.heapify(A)

    for i in range(M):
        t = heapq.heappop(A)
        heapq.heappush(A, t/2)
    
    ans = 0
    for a in A:
        ans += math.floor(a * -1)
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
import heapq


n, m = list(map(int,input().split()))
a_arr = list(map(int,input().split()))
a_arr = [ i * -1.0 for i in a_arr]
heapq.heapify(a_arr)
for i in range(m):
    n = heapq.heappop(a_arr)
    n = -n
    n = n / 2.0
    heapq.heappush(a_arr, -n)
s = 0
for a in a_arr:
    a = -a
    a = int(a)
    s += a

print(s)

Solution (Python):
import heapq
import math

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(len(A)):
  A[i] = A[i] * -1

heapq.heapify(A)

for _ in range(M):
  el = heapq.heappop(A)
  heapq.heappush(A, math.ceil(el/2))

print(sum(A) * -1)

Solution (Python):
N,M = map(int,input().split())
A = list(map(int,input().split()))

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

hq = Heapq(A,desc=True)
for _ in range(M):
    highest = hq.pop()
    hq.push(int(highest/2))
ans = 0
for _ in range(N):
    ans += hq.pop()
print(ans)

Solution (Python):
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 = map(int, input().split())
a = list(map(int, input().split()))
b = Heapq(a, True)
ans = sum(a)
while m > 0:
  i = b.pop()
  t = i // 2
  ans -= i - t
  b.push(t)
  m -= 1
print(ans)

Solution (Python):
from heapq import heappush, heappop, heapify

def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    heap = []

    for i in a:
        heappush(heap, -i)

    for i in range(m):
        max_price = heappop(heap) * -1
        discount_price = max_price // 2
        heappush(heap, -discount_price)

    print(sum(heap) * -1)





resolve()

Solution (Python):
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
while M > 0:
	A = sorted(A, reverse=True)
	M -= 1
	A[0] = mx = A[0]//2
	for i in range(1, N):
		if M > 0:
			if A[i] > mx:
				A[i] = A[i]//2
				M -= 1
			else: break
		else: break
		
print(sum(A))

Solution (Python):
import heapq
n,m = map(int,input().split())
an = [-int(i) for i in input().split()]
heapq.heapify(an)
hpop = heapq.heappop
hpush = heapq.heappush

for i in range(m):
  v = hpop(an) 
  hpush(an,-(-v//2))
print(-sum(an))

Solution (Python):
import heapq
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
a = [(-x,x) for x in a]
heapq.heapify(a)
for i in range(m):
    new = a[0][1]//2
    heapq.heappop(a)
    heapq.heappush(a,(-new,new))
a = [a[i][1] for i in range(len(a))]
print(sum(a))

Solution (Python):
import sys
import queue


		
def main():
	n,m = map(int, input().split())
	al=list(map(int, input().split()))
	ppq=queue.PriorityQueue()
	for a in al:
		ppq.put(-a)
	
	for _ in range(m):
		t = ppq.get()
		ppq.put(t/2)
		
		
	rr=0
	while not ppq.empty():
		rr += int(ppq.get())
	print(-rr)
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import heapq
import math
n, m = [int(v) for v in input().split()]
a_s = [-int(v) for v in input().split()]

heapq.heapify(a_s)

for i in range(m):
  max_a = heapq.heappop(a_s)
  heapq.heappush(a_s, max_a/2)

ans = 0
for a in a_s:
  ans += math.floor(-a)
print(ans)

Solution (Python):

import sys
import heapq as q
import math

def solve(N: int, M: int, A: "List[int]"):
    q.heapify(A)
    for _ in range(M):
        Max = q.heappop(A)
        q.heappush(A, math.ceil(Max/2))
    print(-sum(A))



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [-int(next(tokens)) for _ in range(N)]  
    solve(N, M, A)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
h = []
for i in range(n):
    heapq.heappush( h, -a[i])

for _ in range(m):
    cost = heapq.heappop(h)
    heapq.heappush( h, int(cost/2) )

print(-sum(h))

Solution (Python):
import heapq
import math

n,m = map(int,input().split())
a = list(map(int,input().split()))

a = [-1*num for num in a]

heapq.heapify(a)

for i in range(m):
	maximum = heapq.heappop(a)
	add = math.trunc(maximum/2)
	heapq.heappush(a,add)

print(-1 * sum(a))

Solution (Python):
import heapq

NM = input().split(' ')
N = int(NM[0])
M = int(NM[1])
AN = input().split(' ')
An = [ int(i)*(-1) for i in AN ] 
heapq.heapify(An)

for _ in range(M):
    max_num = heapq.heappop(An) * (-1)
    cooponed_num = max_num//2
    heapq.heappush(An,cooponed_num*(-1))
print(sum(An) * (-1))

Solution (Python):
import sys
import math
from heapq import heappush, heappop, heapify

N,M=map(int, raw_input().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: a*-1, A)
heapify(A)

for _ in range(M):
	a=heappop(A)
	a=math.ceil(float(a)/2)
	heappush(A,a)

print int(sum(A)*-1)

Solution (Python):
from heapq import heappop,heappush,heapify
import math

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x:-x,a))

heapify(a)

for i in range(m):
    p = heappop(a)
    heappush(a,math.ceil(p/2))

ans = 0
for _ in range(n):
    p = heappop(a)
    ans += -p

print(ans)

Solution (Python):
n, m = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)

while m > 0:
    a = sorted(a, reverse=True)
    temp = a[0] // 2
    for i in range(n):
        if a[i] >= temp:
            a[i] = a[i]//2
            m -= 1
            if m <= 0:
                break
        else:
            break

count = 0
for i in a:
    count += i
print(count)

Solution (Python):
import heapq
n, m = map(int, input().split())

a = list(map(int, input().split()))
a = [-ai for ai in a]
heapq.heapify(a)

for i in range(m):
    v = heapq.heappop(a) / 2
    heapq.heappush(a, v)
    
for i in range(n):
    a[i] = int(a[i])
print(-(sum(a)))

Solution (Python):
import sys
from pprint import pprint

import heapq

n, m = map(int, sys.stdin.readline().strip().split(" "))
a = list(map(int, sys.stdin.readline().strip().split(" ")))

q = []
for a_i in a:
    heapq.heappush(q, -1 * a_i)

for _ in range(m):
    price = heapq.heappop(q)
    heapq.heappush(q, ((-1 *price) // 2) * -1)


print(-1 * sum(q))

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]

from heapq import heapify, heappop, heappush
heapify(A)

for i in range(M):
    cur_max = heappop(A)
    new = -((-cur_max) // 2)

    heappush(A, new)


print(-sum(A))

Solution (Python):
from heapq import heapify, heappush, heappop


def main():
    n, m = [int(x) for x in input().split()]
    a = [(-int(x), int(x)) for x in input().split()]

    heapify(a)
    

    for _ in range(m):
        x = (heappop(a))[1] // 2
        heappush(a, (-x, x))
        

    print(sum([y for x, y in a]))


main()

Solution (Python):
import heapq
import math

n, m = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))
a = [(-x, x) for x in a]


heapq.heapify(a)


for i in range(m):
    j = heapq.heappop(a)
    k = math.floor(j[1]/2)
    heapq.heappush(a, (-k, k))


sum_v = 0
for i in a:
    sum_v += i[1]
print(sum_v)

Solution (Python):





from sys import stdin,setrecursionlimit

import heapq
setrecursionlimit(10**6)
input=stdin.readline

n,m=map(int,input().split())
a=[-int(i) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    now=-heapq.heappop(a)
    now//=2
    heapq.heappush(a,-now)

print(-sum(a))

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
import heapq

def main():
    n, m = list(map(int, input().strip().split()))
    v = list(map(lambda x: -x, map(int, input().strip().split())))
    q = []
    for item in v:
        heapq.heappush(q, item)
    for _ in range(m):
        p = heapq.heappop(q)
        
        heapq.heappush(q, (p+1) // 2)
    print(-sum(q))

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))

from heapq import heappush, heappop, heapify

B = []
for i in range(N):
    B.append(-A[i])
    
heapify(B)

cnt=0
while cnt<M:
    tmp = heappop(B)
    heappush(B, -(-tmp//2))
    cnt+=1
    
print(sum(B)*(-1))

Solution (Python):
import heapq
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):
    m = heapq.heappop(A)
    m = -((m*(-1))//2)
    heapq.heappush(A,m)
print(-sum(A))

Solution (Python):
import heapq

N,M = (int(i) for i in input().split())
A = map(int,input().split())
A = list(map(lambda x: -1*x,A))
A.sort()
for i in range(M):
    item = heapq.heappop(A)
    if item % 2== 0:
        heapq.heappush(A,item//2)
    else:
        heapq.heappush(A,item//2+1)


print(-1*sum(A))

Solution (Python):
n,m = map(int,input().split())

a = list(map(int,input().split()))

p = 0
q = -1
list.sort(a,reverse= True)


for i in range(m):
  x = int(a[p]/2)
  a[p] = x
  if(q == -1):
    q = x

  if(p == n -1):
    q = -1
    p = 0
    list.sort(a,reverse=True)
  elif(a[p+1] < q):
    q = -1
    p = 0
    list.sort(a,reverse=True)
  else:
    p += 1


print(sum(a))

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
a = inpl()
hq = []
heapq.heapify(hq)
ans = 0
for i in range(n):
    tt = a[i]
    heapq.heappush(hq,-tt)
for i in range(m):
    tmp = heapq.heappop(hq)
    tmp /= 2
    heapq.heappush(hq,tmp)
    
for i in range(n):
    tttt = heapq.heappop(hq)
    ans -= math.ceil(tttt)
print(ans)

Solution (Python):
import heapq

from collections import deque

N,M = list(map(int, input().split()))
A = list(map(lambda i: -i, map(int, input().split())))


heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    
    heapq.heappush(A,-((-a)//2))

print(-sum(A))

Solution (Python):
import heapq

N,M = map(int, raw_input().split())
A = map(int, raw_input().split())
h = []
for a in A:
    heapq.heappush(h, (-a,a))

for i in range(M):
    
    a = int(heapq.heappop(h)[1]/2)
    heapq.heappush(h, (-a,a))


print sum([x[1] for x in h])

Solution (Python):

import heapq
import numpy as np

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



N,M=acinput()
A=list(map(lambda x:-int(x),input().split(" ")))

A=sorted(A,reverse=False)

for i in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,np.ceil(a/2))

res=0
for sa in A:
    res+=sa

print(int(-res))

Solution (Python):
import heapq

n,m = map(int,raw_input().split())
a = map(int,raw_input().split())
h = []
for x in a:
	heapq.heappush(h, -1*x)
for i in xrange(m):
	x = heapq.heappop(h)
	new = (-1*x) >> 1
	heapq.heappush(h, -1*new)
res = 0
for i in xrange(n):
	res += heapq.heappop(h)
print -1*res

Solution (Python):
"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) 
A = [int(input()) for _ in range(N)] 
lst = [list(map(int,input().split())) for i in range(M)] 
"""

import heapq

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

heap = []
for i in range(N):
  heapq.heappush(heap, -A[i])
  
for i in range(M):
  max_price = heapq.heappop(heap)
  heapq.heappush(heap, max_price / 2.0)

ans = 0
for i in range(N):
  ans += -int(heap[i])

print(ans)

Solution (Python):
import heapq as hp
import sys
input = sys.stdin.readline

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

q = []
for a in A:
    hp.heappush(q, -a)

for i in range(M):
    
    b = hp.heappop(q)

    c = b//2
    if b % 2 != 0:
        c += 1
    hp.heappush(q, c)

ans = 0
for a in q:
    ans += -a
print(ans)

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

Solution (Python):
import heapq
n, m = map(int,input().split())

a = [-i for i in list(map(int, input().split()))]

heapq.heapify(a)

for _ in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a,int(tmp/2))

print(abs(sum(a)))

Solution (Python):

import sys

import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, m = readmi()
t = readt()
h = []
for i in t:
    a = i * (-1)
    heapq.heappush(h, a)
for i in range(m):
    t = heapq.heappop(h)
    t *= -1
    t //= 2
    t *= -1
    heapq.heappush(h, t)
s = 0
for i in h:
    s += i * (-1)
print(s)

Solution (Python):

import sys
import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
a = list(map(int, input().split()))

ha = []

for i in a:
    heapq.heappush(ha, -i)




for _ in range(m):
    heapq.heappush(ha, math.ceil(heapq.heappop(ha)/2))


print(-sum(ha))

Solution (Python):
def solve(N, M, A):
    from math import log, ceil
    from heapq import heappush, heappop, heapify
    Q = [-a for a in A]
    heapify(Q)

    if len(A) == 1:
        return A[0]>>M

    while Q and M:
        a = - heappop(Q)
        b = - Q[0]
        if a == 0:
            continue
        if b == 0:
            k = M
        elif b < a:
            k = min(M, ceil(log(a,2) - log(b, 2)))
        else:
            k = min(M, 1)
        c = a >> k
        
        M -= k
        heappush(Q, -c)
    return sum(-a for a in Q)


def main():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    A = sorted([int(x) for x in input().split()], reverse=True)

    print(solve(N, M, A))

def gen():
    import random
    with open("9", "w") as f:
        print(10**5, 10**5, file=f)
        print(*[random.randint(1, 10**9) for i in range(10**5)],file=f)

main()

Solution (Python):


import heapq

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

Solution (Python):
import heapq as hq

n,m =  map(int,input().split())
ai = list(map(lambda x : -1 *int(x),input().split()))
hq.heapify(ai) 

for _ in range(m):
    saidai = -hq.heappop(ai)
    saidai = -1*(saidai //2)
    
    hq.heappush(ai,saidai)

print(-1*sum(ai))

Solution (Python):


from heapq import heappush,heappop
import math



N,M = map(int, input().split())
An = list(map(int, input().split()))

Hn = []
for a in An:
  heappush(Hn,-a)
for _ in range(M):
  h1 = -heappop(Hn)
  h1 = h1 >> 1
  heappush(Hn,-h1)
print(-sum(Hn))

Solution (Python):
import sys
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


if __name__ == '__main__':
    
    N, M = map(int, input().split())
    A = Heapq(list(map(int, input().split())), desc=True)

    for i in range(M):
        A.push(A.pop() / 2)
    print(-sum([int(i) for i in A.hq]))

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