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

Solution (Python):
import heapq
import math

N, M = map(int, input().split())
A = [ -int(a) for a in input().split() ]
heapq.heapify(A)
for m in range(M):
    heapq.heappush(A, math.ceil(heapq.heappop(A) / 2.0))

print(-sum(A))

Solution (Python):


import heapq

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

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

Solution (Python):
import heapq

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

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

q = []

for a in A:
    heapq.heappush(q, -a)

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

print(-sum(q))

Solution (Python):
from math import ceil
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, ceil(a / 2))

print(-sum(A))

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

Solution (Python):
import heapq
h = []
N, M = map(int, input().split())
As = list(map(int, input().split()))
for i in As:
    heapq.heappush(h, -i)
for _ in range(M):
    i = heapq.heappop(h)
    i = -1 * (-i // 2)
    heapq.heappush(h, i)

print(sum([-1 * heapq.heappop(h) for i in range(len(h))]))

Solution (Python):


import heapq

N,M=map(int,input().split())
l=list(map(int,input().split()))
h=[]
for i in range(N):
    heapq.heappush(h,10**9-l[i])

for i in range(M):
    num=10**9-heapq.heappop(h)
    num=num//2
    heapq.heappush(h,10**9-num)

print(10**9*len(h)-sum(h))

Solution (Python):
import heapq
import math
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,math.ceil(heapq.heappop(h) / 2))
print(sum(h)*(-1))

Solution (Python):
import copy
import heapq
import math
n,m=map(int,input().split())
a=[0]*n
atmp=list(map(int,input().split()))
for i in range(n):
  a[i]=-atmp[i]

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

total=0  
for i in range(n):
  total+=math.ceil(a[i])
print (-total)

Solution (Python):
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi, log2
from copy import deepcopy




def main():
    N,M = map(int, input().split())
    A = []
    list(map(lambda x: heappush(A, -1*int(x)), input().split()))
    for _ in range(M):
        a = -1*heappop(A)
        heappush(A, a//2 * -1)
    ans = 0
    for _ in range(N):
        ans += -1 * heappop(A)
    print(ans)

if __name__ == '__main__':
    main()

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

while m > 0:
    bb = ((heapq.heappop(b) * (-1)) // 2) * (-1)
    heapq.heappush(b, bb)
    m -= 1

total = 0
for i in range(n):
    total += b[i] * -1

print(total)

Solution (Python):
import heapq

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

heapq.heapify(A)
for i in range(M):
    heapq.heappush(A,-(-heapq.heappop(A)//2))
                   
print(-sum(A))

Solution (Python):
import heapq

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

heapq.heapify(AA)

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


print(sum(AA)* -1)

Solution (Python):
def calc(N, M, A):
    if (N == 1):
        return A[0] // (2 ** M)
    A.sort(key=lambda a: -a)
    B = [A]
    for _ in range(M):
        i = 0
        m = B[0][0] if B[0] else -1
        for j in range(1, len(B)):
            if (B[j] and B[j][0] > m):
                i = j
                m = B[j][0]
        p = B[i].pop(0) // 2
        if (len(B) == i + 1):
            B += [[]]
        B[i + 1] += [p]
        if (not (B[0])):
            B.pop(0)
    return sum([sum(b) for b in B])


(N, M) = tuple([int(s) for s in input().split(' ')])
A = [int(s) for s in input().split()]
print(calc(N, M, A))

Solution (Python):
import time
import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
start = time.time()
ans = []
for a in A:
    heapq.heappush(ans, -a)

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

print(-sum(ans))

Solution (Python):
import heapq

def minus_int(s):
  return -1 * int(s)

N, M = map(int, input().split())
A = list(map(minus_int, input().split()))
heapq.heapify(A)
for _ in range(M):
  tmp = int(heapq.heappop(A) / 2)
  heapq.heappush(A, tmp)

print(sum(A) * (-1))

Solution (Python):
import heapq
def func():
    N, M = map(int, input().split())
    A = list(map(lambda x: -int(x), input().split()))
    heapq.heapify(A)

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

if __name__ == '__main__':
    func()

Solution (Python):

import heapq


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


ans = [-a for a in A]
heapq.heapify(ans)
for i in range(M):
    tmp = heapq.heappop(ans) * (-1) // 2
    heapq.heappush(ans, tmp * (-1))
ans = [-a for a in ans]


print(sum(ans))

Solution (Python):
N, M = map(int, input().split())  
A = list(map(int, input().split()))  
A.sort(reverse=True)
i = 0
for _ in range(M):
    A[i] = A[i] // 2
    if i <= N - 2 and A[i] < A[i + 1] and A[0] < A[i+1]:
        i += 1
    else:
        A.sort(reverse=True)
        i = 0
print(str(sum(A)))

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

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

pop = lambda: -heappop(a_minus)
push = lambda x: heappush(a_minus,-x)

for _ in range(m):
    x = pop()
    push(x//2)

print(-sum(a_minus))

Solution (Python):
import math
import heapq

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

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

amount = 0
for a in A:
  amount += math.floor(-a)
print(amount)

Solution (Python):
import math
import heapq

n, m = map(int, input().split())
prices = list(map(int, input().split()))
hq = []


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt



for price in prices:
    _heappush_max(hq, price)


for _ in range(m):
    target = _heappop_max(hq)
    _heappush_max(hq, target/2)

total = 0
for price in hq:
    total += math.floor(price)

print(total)

Solution (Python):
n, m = map(int,input().split())
A = list(map(int,input().split()))
A = [x * -1 for x in A]
A.sort()
import heapq
import bisect
heapq.heapify(A)
for _ in range(m):
    min_ = heapq.heappop(A)
    tmp = min_ * -1 // 2 * -1
    index = bisect.bisect_left(A, tmp)
    heapq.heappush(A,tmp)
print(sum(A) * -1)

Solution (Python):
N, M = map(int, input().split())  
A = list(map(int, input().split()))  
A.sort(reverse=True)
i = 0
for _ in range(M):
    A[i] = A[i] // 2
    if i <= N - 2 and A[i] < A[i + 1] and A[0] < A[i+1]:
        i += 1
    else:
        A.sort(reverse=True)
        i = 0
print(str(sum(A)))

Solution (Python):
def f():
  N,M=map(int,input().split())
  *A,=map(int,input().split())
  l=[]
  for a in A:
      k=a
      while k>=1:
          l+=[k-k//2]
          k=k//2
  print(sum(A)-sum(sorted(l)[-M:]))
if __name__=="__main__":
  f()

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):
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))

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, int(max_/2))
    
    print(- sum(queue))


if __name__ == '__main__':
    main()

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

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

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

print(-sum(q))

Solution (Python):
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)
while m != 0:
    price = heapq.heappop(a) * (-1)
    price //= 2
    m -= 1
    heapq.heappush(a, (-1) * price)
print(sum(a) * (-1))

Solution (Python):
from heapq import heappop,heappush,heapify
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7) 
 
n,m = map(int,input().split())
a = [int(x) for x in input().split()]
 
a_minus = [-x for x in a]
heapify(a_minus)
 
pop = lambda: -heappop(a_minus)
push = lambda x: heappush(a_minus,-x)
 
for _ in range(m):
    x = pop()
    push(x//2)
 
print(-sum(a_minus))

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

Solution (Python):
import heapq
n,m=map(int,input().split())
item=list(map(lambda x: -int(x),input().split()))
heapq.heapify(item)

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

print(-sum(item))

Solution (Python):
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))

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

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

for i in range(M):
    a = heapq.heappop(lst)
    a = a/2.0
    heapq.heappush(lst,a)
    

ans=0
for i in lst:
    i *= (-1)
    
    ans += i//1
print(int(ans))

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

print(-sum(item))

Solution (Python):
import heapq
n,m=map(int,input().split())
q=[]
a=[-int(i) for i in input().split()]
for i in a:
    heapq.heappush(q,i)
ans=chk=0
for i in range(m):
    x=heapq.heappop(q)
    heapq.heappush(q,-(-x//2))
print(-sum(q))
exit()

Solution (Python):
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)
while m != 0:
    price = heapq.heappop(a) * (-1)
    price //= 2
    m -= 1
    heapq.heappush(a, (-1) * price)
print(sum(a) * (-1))

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

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

Solution (Python):


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

l = []
for i in range(N):
    num = A[i]
    while num > 0:
        l.append(num)
        num = int(num / 2)

l.sort(reverse = True)

s = sum(A)
p = 0

if len(l) >= M:
    for i in range(M):
        p += l[i] - int(l[i] / 2)

    print(s - p)
    
else :
    print(0)

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

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

print(-sum(h))

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

Solution (Python):
import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))

def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M 
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    if ls2!=[]:
        ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1


s=sum(ls3)+sum(ls[b+1:])
print(s)

Solution (Python):
import sys

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

	N, M = list(map(int,input().strip().split()))
	A = list(map(int,input().strip().split()))
	A.sort(reverse=True)

	count = [0]*N
	ind = [0]
	for i in range(M):
		maximum = 0
		for j in ind:
			if A[j]>maximum:
				maxind = j
				maximum = A[j]

		if maximum==0: break

		
		A[maxind] = A[maxind]/2
		count[maxind] += 1
		
		if count[maxind]==len(ind):
			ind.append(0)
			
			ind[-2] = min(N-1,ind[-2]+1)
			
		else: 
			
			ind[count[maxind]-1] = min(N-1,ind[count[maxind]-1]+1)

		

	print(sum(map(int,A)))

if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
A = list(map(int, input().split()))
A = map(lambda x: x * (-1), A)
A = sorted(A)

from heapq import heappush, heappop

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

print(sum(A)*(-1))

Solution (Python):
import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))

def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M 
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1


s=sum(ls3)+sum(ls[b+1:])
print(s)

Solution (Python):
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))

Solution (Python):
import math
n, m = map(int, input().split())
an = list(map(int, input().split()))
maxi = max(an)
p = math.floor(math.log2(maxi))+1
ps = [0 for _ in range(p)]
for a in an:
  ps[math.floor(math.log2(a))] += 1

an.sort(reverse=True)

sum = 0
subtotal = 0
for p in ps[::-1]:
  if sum + subtotal + p > m:
    break
  subtotal += p
  an[:subtotal] = [a/2 for a in an[:subtotal]]
  sum += subtotal

an.sort(reverse=True)
p = m - sum
an[:p] = [a/2 for a in an[:p]]


sum = 0
for a in an:
  sum += math.floor(a)
print(sum)

Solution (Python):
import heapq
import math
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):
    aa = heapq.heappop(a)
    aa = math.ceil(aa/2)
    heapq.heappush(a,aa)
print(-sum(a))

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

a.sort(reverse=True)

for i in range(m):
    if i == 0:
        down = a[0]
        a.remove(down)
        b.append(down//2)
    else:
        if a != [] and a[0] >= b[0]:
            down = a[0]
            a.remove(down)
        else:
            down = b[0]
            b.remove(down)
        b.append(down//2)
    
print(sum(a)+sum(b))

Solution (Python):
import numpy as np




N,M = list(map(int, input().split()))
As = np.array(list(map(int, input().split())))


As[::-1].sort()
max_A = As[0]

while M > 0:
    i=1
    for i in range(1, min(M, N)):
        if As[i] <= max_A//2:
            break
    
    
    
    As[:min(M,i)] = As[:min(M,i)] // 2
    
    M -= i
    As[::-1].sort()
    max_A = As[0]
    

print(np.sum(As))

Solution (Python):

import heapq


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


ans = [-a for a in A]
heapq.heapify(ans)
for i in range(M):
    tmp = heapq.heappop(ans) * (-1) // 2
    heapq.heappush(ans, tmp * (-1))
ans = [-a for a in ans]


print(sum(ans))

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

import heapq

heapq.heapify(A)

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

print(-1*sum(A))

Solution (Python):
import heapq
N, M = map(int, input().split())
L = list(map(int, input().split()))
q = []

for money in L:
    tmp = money*(-1)
    heapq.heappush(q, tmp)

for i in range(M):
    kakaku = heapq.heappop(q)*(-1)
    kakaku = int(kakaku/2)
    kakaku = kakaku*(-1)
    heapq.heappush(q, kakaku)

ans=0
while len(q)>0:
    ans += heapq.heappop(q)*(-1)

print(ans)

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

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

A = [int(i)*(-1) for i in input().split()]









heapq.heapify(A)

for i in range(M):
	

	min = heapq.heappop(A)
	
	
	

	heapq.heappush(A,int(min/2))
	


print(sum(A)*(-1))

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

b=[]

for i in range(n):
    for j in range(1+math.floor(math.log(a[i]+0.1)/math.log(2))):
        b.append(a[i]//(2**j)-a[i]//(2**(j+1)))
        
b.sort()
bb=b
b=[bb[len(b)-1-i] for i in range(len(bb))]


print(sum(a)-sum(b[0:m]))

Solution (Python):
import numpy as np
import heapq
N,M=map(int,input().split())
cost = list(map(int,input().split()))
ln=np.array(cost)
ln=ln*-1
cost=ln.tolist()
heapq.heapify(cost)
for i in range(M):
    v=heapq.heappop(cost)/2
    heapq.heappush(cost,v)
su=0
for i in range(len(cost)):
    x=-cost[i]
    su=su+int(x)
print(su)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline






















def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,M = inputMap()
	A = inputList()

	if len(A) == 1:
		print(A[0] // (2**M))
		sys.exit()

	A.sort()
	A = A[::-1]
	ans = 0
	A_new = []
	mimi = -1

	for i in range(1000000000000):
		for i,val in enumerate(A):
			if i == len(A)-1:
				A_new.append(val)
				break

			if mimi < val and M > 0:
				flg = False
				for j in range(1,M+1):
					if M - j != 0:
						tmp = val // (2**j)
						if tmp < A[i+1] or tmp < mimi:
							M -= j
							A_new.append(tmp)
							flg = True
							if mimi == -1:
								mimi = tmp
							break

				if flg == False:
					tmp = val // (2**M)
					M = 0
					A_new.append(tmp)

			else:
				A_new.append(val)

		
		
		A = A_new
		A.sort()
		A = A[::-1]
		A_new = []
		mimi = -1

		if M == 0:
			break

	

	ans = 0
	for i in A:
		ans += i

	print(ans)


if __name__ == "__main__":
	main()

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

def main():
    _,M=map(int,input().split())
    A = []
    for a in list(map(int, input().split())):
        heapq.heappush(A, -a)
    while M>0:
        a = -heapq.heappop(A)
        a //= 2
        M -= 1
        heapq.heappush(A, -a)
    print(-sum(A))

if __name__ == '__main__':
    main()

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

def main():
    input = lambda: stdin.readline()[:-1]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    price = list(map(lambda x: x * -1, A))
    heapify(price)
    for _ in range(M):
        n = heappop(price)
        heappush(price, -(-n // 2))

    print(-sum(price))

main()

Solution (Python):
D = input().split(' ')
N = int(D[0])
M = int(D[1])
D2 = input().split(' ')

A = []
for i in D2:
  A.append(int(i))

A.sort(reverse=True)

used = 0

while True:
  max = A[0]
  n = 0
  while True:
    if A[n] >= int(max / 2):
      A[n] = int(A[n] / 2)
      used = used + 1
    else:
      break
      
    n = n + 1

    if n == N or used == M:
      break
      
  if used == M:
    break
    
  A.sort(reverse=True)
    
sum = 0
for i in range(N):
  sum = sum + A[i]
  
print(sum)

Solution (Python):

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

resid = M
i = 0
pi = 0
pif = True
while resid:
    A[i] //= 2
    resid -= 1
    if i < N-1 and A[i] < A[i+1]:
        if A[pi] > A[i+1]:
            A.sort(reverse=True)
            i = 0
            pi = 0
            pif = True
            continue
        if pif:
            pi = i
            pif = False
        i += 1
    else:
        i = pi
        pif = True

print(sum(A))

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline






















def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,M = inputMap()
	A = inputList()

	if len(A) == 1:
		print(A[0] // (2**M))
		sys.exit()

	A.sort()
	A = A[::-1]
	ans = 0
	A_new = []
	mimi = -1

	for i in range(10000000000000000000):
		for i,val in enumerate(A):
			if i == len(A)-1:
				A_new.append(val)
				break

			if mimi < val and M > 0:
				flg = False
				for j in range(1,M+1):
					if M - j != 0:
						tmp = val // (2**j)
						if tmp < A[i+1] or tmp < mimi:
							M -= j
							A_new.append(tmp)
							flg = True
							if mimi == -1:
								mimi = tmp
							break

				if flg == False:
					tmp = val // (2**M)
					M = 0
					A_new.append(tmp)

			else:
				A_new.append(val)

		
		
		A = A_new
		A.sort()
		A = A[::-1]
		A_new = []
		mimi = -1

		if M == 0:
			break

	

	ans = 0
	for i in A:
		ans += i

	print(ans)


if __name__ == "__main__":
	main()

Solution (Python):
import heapq

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

for _ in range(M):
    v = heapq.heappop(A)
    if v == 0:
        break
    v = -(-v // 2)
    heapq.heappush(A, v)

print(-1*sum(A))

Solution (Python):
from heapq import heappop, heappush
N, M = map(int, input().split())
A = list(map(int, input().split()))
h = []
for a in A:
    heappush(h, a*-1)

for i in range(M):
    val = heappop(h)*-1
    heappush(h, (val//2)*-1)

print(sum(h)*-1)

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

Solution (Python):
import math

n, m = (int(i) for i in input().split())
alist = list(int(i) for i in input().split())
alist=sorted(alist)
blist=[]
clist=[]
for al in alist:
    blist.append(math.floor(math.log(al, 2)))
    clist.append(0)


nowcount=0
now=n-1
while nowcount<=m:
    
    if now!=0:
        if blist[now-1]==blist[now]-clist[now]:
            now-=1
        else:
            if nowcount+n-now<=m:
                nowcount+=(n-now)
                clist[now]+=1
            else:
                amari=(m-nowcount)
                
                nowcount+=(n-now)
    else:
        if nowcount+n-now<=m:
            nowcount+=(n-now)
            clist[now]+=1
        else:
            amari=(m-nowcount)
            
            nowcount+=(n-now)
answer=0
now=0
option=0
dlist=[]
for i in range(n):
    nowat=alist[i]
    now+=clist[i]
    for i in range(now+option):
        nowat=nowat//2
    dlist.append(nowat)

dlist=sorted(dlist)
for i in range(amari):
    dlist[n-i-1]=dlist[n-i-1]//2

print(sum(dlist))

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline






















def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,M = inputMap()
	A = inputList()

	if len(A) == 1:
		print(A[0] // (2**M))
		sys.exit()

	A.sort()
	A = A[::-1]
	ans = 0
	A_new = []
	mimi = -1

	for i in range(10000000000000000000):
		for i,val in enumerate(A):
			if i == len(A)-1:
				A_new.append(val)
				break

			if mimi < val and M > 0:
				flg = False
				for j in range(1,M+1):
					if M - j != 0:
						tmp = val // (2**j)
						if tmp < A[i+1] or tmp < mimi:
							M -= j
							A_new.append(tmp)
							flg = True
							if mimi == -1:
								mimi = tmp
							break

				if flg == False:
					tmp = val // (2**M)
					M = 0
					A_new.append(tmp)

			else:
				A_new.append(val)

		
		
		A = A_new
		A.sort()
		A = A[::-1]
		A_new = []
		mimi = -1

		if M == 0:
			break

	

	ans = 0
	for i in A:
		ans += i

	print(ans)


if __name__ == "__main__":
	main()

Solution (Python):
import numpy as np

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

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

A.append(-1)




Val = sorted(A,reverse=True)



hoge =Val[0]

if N==1:
    print(Val[0]//(2**M))
    exit(0)
if M==1:
    Val[0]//=2
    print(sum(Val)+1)
    exit(0)









i=0
while i<M:
    
    i+=1
    Val[0]//=2
    if i>=M:
        break
    for j in range(1,M):
        if i<M and Val[0]<Val[j]:
            Val[j]//=2
            i+=1
        else:
            Val = sorted(Val,reverse=True)
            break
    


print(sum(Val)+1)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline






















def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,M = inputMap()
	A = inputList()

	if len(A) == 1:
		print(A[0] // (2**M))
		sys.exit()

	A.sort()
	A = A[::-1]
	ans = 0
	A_new = []
	mimi = -1

	for i in range(1000000000000):
		for i,val in enumerate(A):
			if i == len(A)-1:
				A_new.append(val)
				break

			if mimi < val and M > 0:
				flg = False
				for j in range(1,M+1):
					if M - j != 0:
						tmp = val // (2**j)
						if tmp < A[i+1] or tmp < mimi:
							M -= j
							A_new.append(tmp)
							flg = True
							if mimi == -1:
								mimi = tmp
							break

				if flg == False:
					tmp = val // (2**M)
					M = 0
					A_new.append(tmp)

			else:
				A_new.append(val)

		
		
		A = A_new
		A.sort()
		A = A[::-1]
		A_new = []
		mimi = -1

		if M == 0:
			break

	

	ans = 0
	for i in A:
		ans += i

	print(ans)


if __name__ == "__main__":
	main()

Solution (Python):
import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
arr = []
for v in a:
    v*=-1
    heapq.heappush(arr,v)
cur=0
while(m>0 and len(arr)>0):
    next = heapq.heappop(arr)
    next = abs(next)
    next//=2
    if next>0:
        next*=-1
        heapq.heappush(arr,next)
    m-=1
for v in arr:
    cur+=abs(v)
print(cur)

Solution (Python):
import sys, math
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
l = int(math.log2(a[-1]))+1
for i in range(1, l+1):
    for j in range(n):
        b = a[n-1-j]
        if b >> (l-i): 
            a[n-1-j] = b >> 1
            m -= 1
        else: break
        if m == 0:
            print(sum(a))
            sys.exit()
    a.sort()
print(sum(a))

Solution (Python):
import bisect
import heapq
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        hq = []
        for c in input().split():
            heapq.heappush(hq, -1 * int(c))

        for _ in range(M):
            heapq.heappush(hq, int(heapq.heappop(hq) / 2))

        print(-1 * sum(hq))



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):
import heapq
n, m = map(int, input().split())
a = list( map(int, input().split())) 
ans = sum(a)
a = [(-x, x) for x in a]
heapq.heapify(a)


for i in range(m):
    minusaa, aa  = heapq.heappop(a)
    ans -= aa
    heapq.heappush(a, (-(aa//2), aa//2))
    ans += aa//2

print(ans)