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):
from heapq import *
n, m = [int(x) for x in input().split()]
As = [int(x) for x in input().split()]
heap = []
[heappush(heap, -a) for a in As]
for _ in range(m):
    big = -heappop(heap)
    heappush(heap, -(big//2))
print(-sum(heap))

Solution (Python):
import heapq
N,M=map(int, input().split())
A=[-a for a in map(int, input().split())]
A.sort()
for i in range(M):
    a=heapq.heappop(A)
    if a%2==1:
        heapq.heappush(A,a//2+1)
    else:
        heapq.heappush(A,a//2)
    
print(-sum(A))

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

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

que=list(map(lambda x: -int(x),input().split()))
heapify(que)

while m:
    res=-heappop(que)
    res>>=1
    heappush(que,-res)
    m-=1

print(-sum(que))

Solution (Python):
import heapq

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

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

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

    while M:
        m = heappop(A)
        heappush(A, math.ceil(m/2))
        M -= 1
    print(-sum(A))

if __name__ == '__main__':
    solve()

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

Solution (Python):
from heapq import heappush as push, heappop as pop
N, M = [int(v) for v in raw_input().split()]
items = [- int(v) for v in raw_input().split()]
q = []
for i in items:
    push(q, i)
for ticket in range(M):
    price = -pop(q)
    push(q, -(price//2))
tot= -sum(q)
print(tot)

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

if __name__ == "__main__":
    f_d()

Solution (Python):
import heapq

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

heapq.heapify(A)


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

for i in range(N):
    A[i] = (-A[i])//1


print(int(sum(A)))

Solution (Python):
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = [-A[i] for i in range(N)]
A = sorted(A)
cnt = 0
while cnt<M:
    a = heapq.heappop(A)*(-1)
    a = a/2
    heapq.heappush(A,-a)
    cnt += 1
A = [int(-A[i]) for i in range(N)]
print(sum(A))

Solution (Python):
import heapq

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

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

valueheap = [x * (-1) for x in a]

heapq.heapify(valueheap)

for _ in range(M):

    maxvalue = heapq.heappop(valueheap) * (-1)

    maxvalue //= 2

    maxvalue *= -1

    heapq.heappush(valueheap, maxvalue)

print(sum(valueheap) * (-1))

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

Solution (Python):
import heapq
N,M = map(int,input().split())
A = list(map(lambda x:-int(x),input().split()))
heapq.heapify(A)
m = 0
while m<M:
    m+=1
    a = heapq.heappop(A)
    heapq.heappush(A,a/2)
print(sum([-int(a) for a in A]))

Solution (Python):

import sys
import heapq

def solve(N: int, M: int, A: "List[int]"):
    
    
    
    

    mA = [-1*i for i in A]
    heapq.heapify(mA)
    

    for i in range(M):
        x = heapq.heappop(mA)*(-1)
        x = x // 2
        heapq.heappush(mA, -1*x)

    print(-1*sum(mA))
    return



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):
from heapq import heappush, heappop, heapify
N, M = map(int, input().split())
a = [-int(a) for a in input().split()]
heapify(a)
for _ in range(M):
  heappush(a, heappop(a) / 2)
print(-sum(int(x) for x in a))

Solution (Python):
import sys
import heapq
import math


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [int(s) for s in sys.stdin.readline().strip().split()]

    q = []
    for ai in a:
        heapq.heappush(q, - ai)

    for i in range(m):
        value = heapq.heappop(q)
        discounted = math.ceil(value / 2)
        heapq.heappush(q, discounted)

    print(- sum(q))


main()

Solution (Python):


import heapq

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

    heapq.heapify(A)

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

        heapq.heappush(A, -a)        
    
    print(-sum(A))



if __name__ == '__main__':
    main()

Solution (Python):
import sys; from collections import deque; readline = sys.stdin.readline;

from heapq import heappush, heappop

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

heap = []

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

for i in range(M):
    a = heappop(heap)
    heappush(heap, -((-a) // 2))

total = -sum(heap)

print(total)

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

n, m = map(int, input().split())
q = []
for x in input().split():
    heappush(q, -int(x))

for i in range(m):
    item = (-heappop(q))//2
    heappush(q, -item)

print(-sum(q))

Solution (Python):
import heapq

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

Solution (Python):
import heapq
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort(reverse = True)
que = []
def div(a,b):
    if a % b == 0:
        return a//b
    else:
        return a//b + 1
for i in range(n):
    heapq.heappush(que,-a[i])
for i in range(m):
    p = heapq.heappop(que)
    p = div(p,2)
    heapq.heappush(que,p)
print(-sum(que))

Solution (Python):
from heapq import heapify, heappush, heappop
def solve():
    n, m = map(int, input().split())
    A = [-int(i) for i in input().split()]
    heapify(A)
    for _ in range(m):
        heappush(A, -(-heappop(A) // 2))
    print(-sum(A))
solve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
import heapq
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    A=list(map(lambda x:-(int(x)),input().split()))
    heapq.heapify(A)
    for _ in range(m):
        a=heapq.heappop(A)
        a=-a
        a=a>>1
        heapq.heappush(A,-a)
    print(-sum(A))

resolve()

Solution (Python):
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)
import heapq








def main():
    N, M = map(int, input().split())
    A = [int(c) for c in input().split()]
    queue = []


    for i in range(N):
        heapq.heappush(queue, - A[i])
    
    for i in range(M):
        max_ = heapq.heappop(queue)
        heapq.heappush(queue, (max_+1)//2)
        
    
    print(- sum(queue))




if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
X = []
C = [0] * N
for j in range(30):
    for i in range(N):
        X.append(((A[i]>>j)<<24) + (i << 6) + j)
X = sorted(X)[::-1]
ans = sum(A)
for a in X[:M]:
    x, i, j = a >> 24, (a >> 6) % (1<<18), a % (1<<6)
    if C[i] == j:
        C[i] += 1
        ans -= x - x//2
print(ans)

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

Solution (Python):
import heapq
N, M = [int(x) for x in input().split()]
h = []
[heapq.heappush(h, -int(x)) for x in input().split()]
for _ in range(M):
    tmp = heapq.heappop(h)
    if (tmp == 0): break
    heapq.heappush(h, -1*(-tmp//2))
print(-1 * sum(h))

Solution (Python):
import heapq
from collections import defaultdict
n, m= [int(i) for i in input().split()]
a = [(-int(i), -int(i)) for i in input().split()]
heapq.heapify(a)

for _ in range(m):
  n, r = heapq.heappop(a)
  rnew = float(r)/2
  nnew = -1 * (-1 * r // 2) 
  heapq.heappush(a, (nnew, rnew))

ans = 0
for an, ar in a:
  ans += -1 * an
print(int(ans))

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

Solution (Python):
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(N):
    heapq.heappush(B,-A[i])

for i in range(M):
    x = -heapq.heappop(B)
    if x == 0:
      break
    x = x//2
    heapq.heappush(B,-x)

print(-sum(B))

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

for i in range(len(a)):
  a[i] *= -1

heapq.heapify(a)

for i in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a,tmp/2)
  
ans = -1 * sum(map(int,a))

print(ans)

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

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

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)

show_flg=False
show_flg=True

an=0
n,m=MI()
a=LI()
q=[]
for i in a:
    heappush(q,-i)

for i in range(m):
    x=-heappop(q)
    x//=2
    heappush(q,-x)
print(-sum(q))

Solution (Python):
import math
import heapq

N, M = map(int, input().split())
A = list(map(int,input().split()))
B = []
for i in range(N):
	heapq.heappush(B, -A[i])

for _ in range(M):
	tmp = heapq.heappop(B) * (-1)
	tmp = math.floor(tmp/2)
	heapq.heappush(B, -tmp)

print(sum(B) * (-1))

Solution (Python):
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

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

sumA = -sum(A)
heapify(A)

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

print(sumA)

Solution (Python):
import heapq

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

h = []
for v in A:
    heapq.heappush(h, -v)

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

print(-sum(h))

Solution (Python):
import heapq

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

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

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
L = LI()
for i in range(n):
    L[i] *= -1


heapify(L)
for i in range(m):
    p = heappop(L)
    heappush(L, -(-p//2))



print(-sum(L))

Solution (Python):
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

import heapq
def solve(N, M, A):
    pq = [-x for x in A]
    heapq.heapify(pq)

    for _ in xrange(M):
        x = -heapq.heappop(pq)
        x /= 2
        heapq.heappush(pq, -x)
    return -sum(pq)


N, M = rrm()
print solve(N, M, rrm())

Solution (Python):
import sys
import collections
import copy
import math
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
N,M =map(int,input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
count = 0
while count != M:
    chk =A[0]//2
    for i in range(len(A)):
        if A[i] >= chk:
            A[i] = A[i]//2
            count += 1
            if count == M:
                break
        else:
            A.sort(reverse=True)
            break
print(sum(A))

Solution (Python):


import sys
import collections
import heapq
sys.setrecursionlimit(4100000)
import math
n,m = [int(i) for i in input().split()]
b = [-int(i) for i in input().split()]
heapq.heapify(b)
for i in range(m):
    temp = heapq.heappop(b)

    temp = temp/2

    heapq.heappush(b,math.ceil(temp))
print(-sum(b))

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):
    a = heapq.heappop(A)
    if a%2 == 0:
        a = a//2
    else:
        a = a//2+1
    heapq.heappush(A,a)
print(sum(A)*(-1))

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import heappop, heappush

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    H = []
    for i in A:
        heappush(H, -i)
    for _ in range(M):
        j = heappop(H)
        j = - ( -j // 2)
        heappush(H, j)
    ans = - sum(H)
    print(ans)

if __name__ == '__main__': main()

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]*=-1
import heapq
heapq.heapify(a)
for i in range(m):
    
    tmp=heapq.heappop(a)
    tmp=tmp*-1
    tmp=tmp//2
    tmp*=-1
    heapq.heappush(a,tmp)

print(sum(a)*-1)

Solution (Python):
from heapq import heappop, heappush
N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A,reverse = True)
hq = []
ans = 0
for i in range(N):
  heappush(hq,-A[i])
for i in range(M):
  heappush(hq,int(heappop(hq)/2))
print(-sum(hq))

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

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

hq.heapify(ls)

for _ in range(m):
  t = -1*hq.heappop(ls)
  hq.heappush(ls,t//2*(-1))
  
print(-1*sum(ls))

Solution (Python):
import sys, math
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():
    def input():
        return sys.stdin.readline()[:-1]
    N, M = map(int,input().split())
    A = sorted(list(map(int,input().split())))[::-1]
    Q = Heapq(A, True)
    for k in range(M):
        now = Q.pop()
        Q.push(now//2)
    ans = 0
    for k in range(N):
        ans += Q.pop()
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import heapq
    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    a = sorted([-i for i in a])
    for i in range(m):
        x = heapq.heappop(a)
        if x%2 == 0:
            x = int(x//2)
        else:
            x = int(x//2)+1
        heapq.heappush(a,x)
    print(sum(a)*(-1))
    
if __name__ == '__main__':
    main()

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

product = [-1*a for a in A]

import heapq


heapq.heapify(product)


for _ in range(M):
    min_val = heapq.heappop(product)
    discount_val = int(min_val / 2)

    
    heapq.heappush(product, discount_val)
    
print(-1*sum(product))

Solution (Python):


import sys
import collections
import heapq
sys.setrecursionlimit(4100000)
import math
n,m = [int(i) for i in input().split()]
b = [-int(i) for i in input().split()]
heapq.heapify(b)
for i in range(m):
    temp = heapq.heappop(b)
    
    temp = temp/2
    
    heapq.heappush(b,math.ceil(temp))
print(-sum(b))

Solution (Python):
import math
import heapq
from itertools import product, permutations,combinations

import sys
def input():
	return sys.stdin.readline().strip()

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

heapq.heapify(A)


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

total = 0
for i in range(N):
	total -= math.ceil(A[i])

print(total)

Solution (Python):
import heapq as hq
def main():
    n,m=map(int,input().split(' '))
    a=[-1*i for i in list(map(int,input().split(' ')))]
    hq.heapify(a)
    for i in range(m):
        a_max = hq.heappop(a)
        a_max = (-1*a_max)//2
        hq.heappush(a,-1*a_max)
    print(-1*sum(a))
if __name__ == '__main__':
    main()

Solution (Python):

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

B = []
for a in A:
    heapq.heappush(B,-a)

for j in range(M):
    b = -heapq.heappop(B)
    b = b//2
    heapq.heappush(B,-b)
    
print(-sum(B))

Solution (Python):
from queue import PriorityQueue
N, M = map(int, input().split())  

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


pq = PriorityQueue()

for i in range(len(A)):
    pq.put(-A[i])

ans = 0

for i in range(M):
    tmp = -(pq.get())
    tmp = tmp//2
    pq.put(-tmp)







while not pq.empty():
    ans += -pq.get()

print(ans)

Solution (Python):


import sys
from heapq import heappush, heappop, heapify

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
A  = [-a for a in LIST()]

heapify(A)
for i in range(M):
    mx = -heappop(A)
    mx //= 2
    heappush(A, -mx)

print(-sum(A))

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

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

heapify(A)


for _ in range(M):
    m = pop(A)
    push(A, math.ceil(m / 2))

print(-sum(A))

Solution (Python):
n, m = map(int, input().split())
ps = list(map(int, input().split()))
s = sum(ps)
ls = []
for p in ps:
    prev = p
    while p > 0:
        p //= 2
        ls.append(prev - p)
        prev = p
ls.sort(reverse=True)
print(s - sum(ls[:m]))

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

Solution (Python):
import numpy as np
import bisect
import heapq

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

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

Solution (Python):
import sys
import math
import bisect
MAX_INT = int(10e12)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

import sys
from collections import deque
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
a = IL()

hpop = heapq.heappop
hpush = heapq.heappush
data = []

for i in a:
    hpush(data, -i)

for i in range(M):
  tmp = math.ceil(hpop(data)/2)
  hpush(data, tmp)
  

print(-sum(data))

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

import heapq

N, M = map(int,input().split())
A = list(map(int, input().split()))
q = []
heapq.heapify(q)
for i in range(N):
    heapq.heappush(q,-A[i])

cnt = M
while cnt>0:
    a=heapq.heappop(q)
    a=-a
    a=a//2
    heapq.heappush(q,-a)
    
    cnt-=1
print(-sum(q))

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

ans = 0
for x in h:
    ans += int(-x)
print(ans)

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

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    heap = []
    for a in A:
        heappush(heap, -a)

    for _ in range(K):
        price = heappop(heap)
        heappush(heap,-(- price//2))

    return -sum(heap)


if __name__ == '__main__':
    print(main())

Solution (Python):
from heapq import heappush as hpush, heappop as hpop

n, m = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())

heap = []
for num in a:
    hpush(heap, -num)

while m > 0:
    x = hpop(heap)
    if x == 0: break
    x = -x
    x /= 2
    hpush(heap, -x)
    m -= 1

ans = 0
while heap:
    x = hpop(heap)
    ans -= x

print ans

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

q = []
for i in range(N):
    heapq.heappush(q, -A[i])

for j in range(M):
    tmp = heapq.heappop(q)
    tmp = - (-tmp // 2)
    heapq.heappush(q, tmp)

ans = -sum(q)
print(ans)

Solution (Python):
import heapq

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

heapq.heapify(A)

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

for i in range(k):
    A[i] = int(A[i] * -1)

ans = sum(A)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


import heapq
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)


def main():
    N, M = input([int, 2])
    A = input([int, N])

    que = heapque()
    for a in A:
        que.push(-a)
    
    for _ in range(M):
        que.push(-(-que.pop() // 2))

    print(-sum(que.que))
    
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

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

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

q = [-ai for ai in a]
heapify(q)

for i in range(m):
    v = heappop(q)
    v = -(abs(v) // 2)
    heappush(q, v)

print(-sum(q))

Solution (Python):
import heapq
import math

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

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

print(-1 * sum(A))

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

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

As = list(map(lambda x : -1 * int(x), input().split()))

heapq.heapify(As)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)


def solve():
    N, M = LI()
    a_list = LI()

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

    import heapq
    heapq.heapify(a_list)

    for i in range(M):
        mn = heapq.heappop(a_list)
        mn = -1*(-1*mn // 2)
        heapq.heappush(a_list, mn)

    print(-1*sum(list(a_list)))


solve()

Solution (Python):
from sys import exit, stderr, stdin
input = stdin.readline

import heapq
def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N, M = [int(n) for n in input().split()]
    A = [-int(n) for n in input().split()]
    heapq.heapify(A)
    while(M):
        targ = heapq.heappop(A)
        targ /= 2
        heapq.heappush(A,targ)
        M-=1

    print(sum([-int(a) for a in A]))



if __name__ == "__main__":
    main()

Solution (Python):
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):
    ma = heapq.heappop(A)
    
    heapq.heappush(A, -(-ma // 2))


print(-sum(A))

Solution (Python):
import heapq

N, M = map(int, input().split())
nums = list(map(int, input().split()))
hp = []
for i in range(N):
  heapq.heappush(hp, -nums[i])
ans = sum(nums)
for _ in range(M):
  num = -heapq.heappop(hp)
  t = num//2
  ans -= num-t
  heapq.heappush(hp, -t)
print(ans)

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

Solution (Python):
from sys import stdin
import heapq
import math

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [-int(x) for x in stdin.readline().rstrip().split()]

heapq.heapify(A)

while M > 0:
    h = heapq.heappop(A)
    h = math.ceil(h / 2)
    heapq.heappush(A, h)
    M -= 1

print(-sum(A))

Solution (Python):
import heapq

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

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

print(-sum(A))

Solution (Python):

import heapq
n,m = map(int, input().split())
q = []
s = 0
for a in input().split():
    a = int(a)
    s += a
    q.append(-a)

heapq.heapify(q)

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

print(-1*sum(q))

Solution (Python):
import sys
from collections import Counter
import math
import heapq
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n, m = na()
a = na()
li = [a[i] * (-1) for i in range(n)]
heapq.heapify(li)
for i in range(m):
    num = heapq.heappop(li) * (-1)
    num = math.floor(num / 2)
    heapq.heappush(li, num * (-1))
ans = 0
for i in range(n):
    ans += (heapq.heappop(li) * (-1))
print(ans)

Solution (Python):
import heapq
import math

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()))

q = Heapq(a, desc=True)

for i in range(m):
    qi = q.pop()
    q.push(math.floor(qi/2))

ans = 0

for i in range(n):
    ans += q.pop()

print(ans)

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