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):
def input_int():
    return(int(input()))

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

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

import heapq

def run():
    n, ticket_count = input_int_map()

    nums = input_int_list()


    nums = list(map(lambda x: x * (-1), nums))  

    heapq.heapify(nums)



    for _ in range(ticket_count):
        num = (heapq.heappop(nums) * (-1))

        num = num // 2

        heapq.heappush(nums, num * (-1))

    nums = list(map(lambda x: x * (-1), nums))
    print(sum(nums))

run()

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

import heapq
a = list(map(lambda x:x*(-1),a))
heapq.heapify(a)

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

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

for i in range (0, N):
	A[i] = -1*A[i]

A = sorted(A)

heapq.heapify(A)

import math

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

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

Solution (Python):
import heapq

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

for i in input().split():
  heapq.heappush(a, -int(i))

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

print(-sum(a))

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

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

print(-sum(A))

Solution (Python):
import heapq


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

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

print(-sum(A))

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

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

abc141d()

Solution (Python):
import heapq

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

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

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

def main():

    
    
    

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

    while M > 0:
        a = -heappop(A)
        a //= 2
        heappush(A, -a)
        M -= 1
    
    ans = 0
    for a in A:
        ans -= a

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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


if __name__ == '__main__':
    main()

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

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]
heapq.heapify(A)

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

Solution (Python):
import heapq



prio = []

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

for num in nums:
    heapq.heappush(prio, -num)

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

print(-sum(prio))

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

heapq.heapify(A)

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

print(-sum(A))

Solution (Python):
import heapq

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

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

print(-sum(A))

Solution (Python):
import heapq

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

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

print(-sum(A))

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

Solution (Python):
from bisect import bisect_left as bs

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

while M > 0:
  i = A.pop(-1) // 2
  A.insert(bs(A, i), i)
  M -= 1

print(sum(A))

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

heapq.heapify(A)

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

print(-sum(A))

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

Solution (Python):
import heapq
n, m = map(int, input().split())
A = sorted(map(lambda x: -int(x), input().split()))
for _ in range(m):
    a = heapq.heappop(A)
    a = -(-a//2)
    heapq.heappush(A, a)

print(-sum(A))

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)
for i in range(m):
    x = heapq.heappop(a)*(-1)//2
    heapq.heappush(a,(x*(-1)))
print(sum(a)*(-1))

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

A = deque(sorted(a,reverse=True))
B = deque([])

for _ in range(m):
    
    if A:
        if B:
            if (A[0] > B[0]):
                B.append(A.popleft()//2)
                continue
        else:
            B.append(A.popleft()//2)
            continue
    b = B.popleft()
    B.append(b//2)

print(sum(A)+sum(B))

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
from heapq import heapify, heappop, heappush
dis = []
for k in range(N):
  dis.append((-(A[k]-A[k]//2), k, 0))
heapify(dis)
while M:
  M -= 1
  item = heappop(dis)
  index = item[1]
  cnt = item[2] + 1
  discount = A[index]//pow(2, cnt) - A[index]//pow(2, cnt+1)
  heappush(dis, (-discount, index, cnt))

ans = 0
while dis:
  item = dis.pop()
  ans += A[item[1]]//pow(2, item[2])

print(ans)

Solution (Python):

"""
Created on Wed Sep 16 17:42:18 2020

@author: liang
"""
"""
【優先度付きキュー】
・ヒープ構造の部分順序付き木
・挿入、削除、最大値（最小値）の取り出し、要素の値の変更
　⇒　O(log n)
・ヒープ生成
　⇒O(n)
 【使い方】
  import heapq
  ●heapq.heapify(list) 
  ●heapq.heapify(list(map(lambda x:int(x)*(-1),list))) 
  ●heapq.heappop(a)
  ●heapq.heappush(a,1)
"""

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

A = [int(x)*(-1) for x in input().split()]
heapq.heapify(A)


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

Solution (Python):
import heapq 

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

Solution (Python):
from heapq import *

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

heapify(a)

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


print(sum(a)*-1)

Solution (Python):

"""
Created on Wed Sep 16 12:35:58 2020

@author: liang
"""

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

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

print(ans)

Solution (Python):
import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

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

if __name__ == '__main__':
    Main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq

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

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

print(-sum(A))

Solution (Python):
import heapq

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

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

Solution (Python):
import heapq
import sys

lines = sys.stdin.readlines()

N, M = [int(n) for n in lines[0].strip().split()]
prices = [-int(n) for n in lines[1].strip().split()]

heapq.heapify(prices)

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

print(-sum(prices))

Solution (Python):
import heapq as hq
N,M=list(map(int, input().split()))
A=list(map(int, input().split()))
B=[(-1)*A[i] for i in range(N)]
B.sort()
for _ in range(M):
  a=hq.heappop(B)
  a=((a*(-1))//2)*(-1)
  hq.heappush(B,a)
C=[-B[i] for i in range(N)]
print(sum(C))

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

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

result = -sum([int(p) for p in hq])
print(result)

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

for m in range(M):
  heappush(A,int(heappop(A)/2))

print(-sum(A))

Solution (Python):
import heapq
import math

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

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

print(-sum(a))

Solution (Python):
import heapq
import math

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

B = [-A[i] for i in range(N)]
heapq.heapify(B)
while M:
    p = heapq.heappop(B)
    p /= 2
    heapq.heappush(B, p)
    M -= 1

ans = 0
for i in range(N):
    ans += math.floor(-B[i])
print(ans)

Solution (Python):


import heapq

def main():
    line1 = input()
    line2 = input()

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

if __name__ == "__main__":
    main()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
import heapq
a = list(map(lambda x: x*(-1), A))  

heapq.heapify(a)
for i in range(K):
  num = heapq.heappop(a)*(-1)
  heapq.heappush(a, -1*(int(num/2)))
  
  if num == 0:
    break
print(-sum(a))

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

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

print(-sum(A))

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

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

Solution (Python):
import heapq

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

while m > 0:
    a_max = heapq.heappop(a)
    if a_max == 0:
        break
    heapq.heappush(a, (-1)*(-a_max // 2))
    m -= 1
print(sum(a)*(-1))

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

a=[-i for i in a]
heapq.heapify(a)
for _ in range(m):
     b=heapq.heappop(a)
     heapq.heappush(a,-((-b)//2))

print(-sum(a))

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

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

    ans = abs(ans)
    return ans

print(main())

Solution (Python):
import heapq

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

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

memo = []
for t in T:
    memo.append(-t)
memo.sort()

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

Solution (Python):
import copy

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

        if left == right:
            return right,tmp

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

    for i in range(N):
        ans += A[i]

    return ans

print(main())

Solution (Python):
import heapq

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

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

Solution (Python):
from heapq import *

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

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = inpl()
a = [-x for x in a]
heapify(a)
for _ in range(m):
    now = heappop(a)
    now /= 2
    heappush(a,now)
    
res = 0
for x in a:
    res += int(-x)
print(res)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


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

heapq.heapify(A)

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

print(-sum(A))

Solution (Python):
import heapq

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

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

while m>0:
    aa=heapq.heappop(q)
    heapq.heappush(q,-((-aa)//2))
    m-=1

print(-sum(q))

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

Solution (Python):
'''
Created on 2020/09/09

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

Solution (Python):
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 _ in range(M):
    a = heapq.heappop(heap)
    a = -a
    a = a//2
    heapq.heappush(heap,-a)
print(-sum(heap))

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
from heapq import heappush, heappop
Q = []

for a in As:
    heappush(Q, -a)

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

print(-sum(Q))

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

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

import heapq,math

heapq.heapify(a)

for _ in range(m):
    b=heapq.heappop(a)*(-1)
    b //=2

    heapq.heappush(a,b*(-1))

print(sum(a)*(-1))

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

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

heapify(arr)

for _ in range(m):
    a = heappop(arr)
    heappush(arr, -(-a // 2))

print(-sum(arr))

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from heapq import *

n,m=nii()
a=lnii()
a=[-i for i in a]
a.sort(reverse=True)

heapify(a)

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

print(-sum(a))

Solution (Python):
import heapq
n, m, *a = map(int, open(0).read().split())
a = list(map(lambda x: -x, a))

heapq.heapify(a)
for i in range(m):
    b = -heapq.heappop(a)
    heapq.heappush(a, -(b >> 1))

print(-sum(a))

Solution (Python):
from heapq import heappop, heappush, heapify
n,m = map(int, input().split())
al = list(map(int, input().split()))
alm = []
for a in al:
    alm.append(a*(-1))

heapify(alm)
for _ in range(m):
    poped = heappop(alm)
    val = (poped*(-1))//2
    heappush(alm, val*(-1))

ans = sum(alm)
print(-ans)

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right 
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]

N,M=mint()
A=lint()
H=[-a for a in A]
heapify(H)
for _ in range(M):
    x = heappop(H)
    x = -(-x//2)
    heappush(H,x)
print(-sum(H))

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

main()

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 _ in range(m):
    heapq.heappush(a, -((-heapq.heappop(a))//2))
print(-sum(a))

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

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

Solution (Python):
import sys
input=sys.stdin.readline 
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):
    h=-heapq.heappop(a)
    h=h//2
    heapq.heappush(a,-h)
print(-sum(a))

Solution (Python):
import bisect

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

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

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

Solution (Python):
n,m=map(int, input().split())
a=[int(x) for x in input().split()]
a=[-1*x for x in a]

import heapq

heapq.heapify(a)

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

a=[-1*x for x in a]
a=[int(x) for x in a]
print(sum(a))

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

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

A = list(map(lambda x: x * (-1), A))

heapify(A)
for i in range(m):
    x = heappop(A)
    x = (x + 1) // 2
    heappush(A, x)

print(-1 * sum(A))

Solution (Python):






import heapq




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





































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

A = map(lambda x: x*(-1), A)
print(sum(A))

Solution (Python):





from collections import deque




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





A = sorted(A, reverse=True)
































queue_A = deque(A)
queue_B = deque()

for i in range(M):
    if len(queue_B) > 0 and queue_B[0] >= queue_A[0]:
        queue_A.appendleft(queue_B.popleft())
    queue_A[0] //= 2
    if len(queue_A) > 1 and queue_A[0] < queue_A[1]:
        queue_B.append(queue_A.popleft())

print(sum(queue_A) + sum(queue_B))

Solution (Python):
import math

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


def is_ok(x):
    cnt = 0
    for a in A:
        while math.floor(a) > x:
            cnt += 1
            a /= 2
        
    return cnt <= M

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

X = bisect(-1, max(A))
ans = 0
cnt = 0
for a in A:
    while math.floor(a) > X:
        cnt += 1
        a /= 2
    ans += math.floor(a)
ans -= math.ceil(X / 2) * (M - cnt)
print(ans)

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

Solution (Python):
import bisect

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

As.sort()



for _ in range(M):
    discount = As.pop(-1)

    if(discount == 0):
        break

    discount //= 2

    i = bisect.bisect_left(As, discount)
    As.insert(i, discount)


print(sum(As))

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):
    x = heappop(a)
    heappush(a, int(x/2))

ans = 0
for i in range(n):
    ans += -a[i]
print(ans)

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

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

print(sum(a)*(-1))

Solution (Python):
import heapq

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

heapq.heapify(A)

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

print(-sum(A))

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

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

heapq.heapify(A)

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

print(abs(sum(A)))

Solution (Python):

from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)





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




def I(): return int(sys.stdin.buffer.readline())





def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()




def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')







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 main():
    n, m = LI()
    a = list(map(lambda x: -x, LI()))
    heapify(a)
    for i in range(m):
        highest = -heappop(a)
        heappush(a, -(highest // 2))
    print(-sum(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 i in range(m):
    x=-heapq.heappop(a)
    heapq.heappush(a,-(x//2))
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 i in range(m):
  heapq.heapreplace(a,a[0]/2)

print(-sum(map(int,a)))

Solution (Python):

import heapq as he

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

for i in range(m):
    he.heappush(a,he.heappop(a)*(-1)//2*(-1))

print(sum(a)*(-1))

Solution (Python):
import heapq

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

heapq.heapify(A)

for _ in range(M):
  v = heapq.heappop(A) * (-1)
  heapq.heappush(A, -(v >> 1))

print(-sum(A))