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 sys
import math
from collections import deque
import heapq

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


def main():
    N, M = NMI()
    A = NLI()
    A = [-a for a in A]
    heapq.heapify(A)
    for i in range(M):
        a_max = -heapq.heappop(A)
        a_max = a_max // 2
        heapq.heappush(A, -a_max)
    print(-sum(A))



if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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

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

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

ans=0
for i in range(0,N):
    ans-=A[i]
print(ans)

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):
    x = heapq.heappop(a)
    heapq.heappush(a, -1 * ((-x) // 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]*=-1
heapq.heapify(a)

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

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

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

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

print(-sum(pq))

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

heapify(A)

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

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

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

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

print(-1*sum(A))

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

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

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

print(-1*sum(A))

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

Solution (Python):
import heapq

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

al = [v*(-1) for v in al]
heapq.heapify(al)

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

print(sum(al)*(-1))

Solution (Python):

"""
Created on Wed Jun  3 18:35:23 2020

@author: NEC-PCuser
"""
import heapq

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

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 = map(int,input().split())
a = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(a)

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

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

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

import heapq
heapq.heapify(A)

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

print(-sum(A))

Solution (Python):


from heapq import heapify, heappop, heappush

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

heapify(a)

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

ans = -sum(a)

print(ans)

Solution (Python):


from heapq import heapify, heappop, heappush

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

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

a = [-1*item for item in a]
ans = sum(list(a))

print(ans)

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 = int((-tmp / 2) // 1)
    heapq.heappush(A, -tmp)
print(-sum(A))

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

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

Solution (Python):
import sys
import heapq

input = lambda: sys.stdin.readline().rstrip()


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

    heapq.heapify(Am)

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

    print(-sum(Am))


if __name__ == '__main__':
    solve()

Solution (Python):
import heapq

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

heapq.heapify(prod)

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

    a = a//2

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


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

print(sum(ans))

Solution (Python):
import queue


def m():
    N, M = map(int, input().split())
    q = queue.PriorityQueue()
    A = list(map(int, input().split()))
    ans = []
    for a in A:
        q.put(-a)
    while M > 0:
        x = -q.get()
        x = -(x >> 1)
        M -= 1
        q.put(x)
    while not q.empty(): ans.append(q.get())
    return abs(sum(ans))


print(m())

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

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

Solution (Python):
import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

n, m = map(int, rl().split())
h = list(map(lambda x: -1*int(x), rl().split()))
heapq.heapify(h)
for _ in range(m):
    heapq.heappushpop(h, math.ceil(h[0]/2))
print(-sum(h))

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

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

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

Solution (Python):
from heapq import heapify, heappop, heappush
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 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 _ in range(m):
    x=heapq.heappop(a)*(-1)
    x=x//2
    heapq.heappush(a,-x)

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

Solution (Python):
import math
import heapq
n, m = map(int, input().split())
a = [int(i) * (-1) for i in input().split()]
heapq.heapify(a)
i = 0
while i < m:
    max_a = - heapq.heappop(a)
    max_a /= 2
    heapq.heappush(a, -max_a)
    i += 1
total = 0
for k in a:
    total += math.floor(-k)
print(total)

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


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = [-ai for ai in a]
    heapify(a)

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

    print(-sum(a))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
import math
import heapq
n,m = map(int, raw_input().split(' '))

heap = [-e for  e in map(int, raw_input().split(' '))]
heapq.heapify(heap)
while(m and heap):
	u = heapq.heappop(heap)
	u *= -1
	u /=2
	if u:
		heapq.heappush(heap, -u)
	m-=1
	"""

	q = int(math.ceil(math.log(u,2)))
	if 2 ** q <= u: q +=1
	if q <= m:
		m-= q
	else:
		u /= 2
		m -=1
		if u:
			heapq.heappush(heap, -u)

	"""
print -sum(heap or [0])

Solution (Python):

import heapq
from functools import reduce
n, m = map(int, input().split())
arr = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(arr)
for i in range(m):
    t = -1 * heapq.heappop(arr)
    heapq.heappush(arr, -1 * (t // 2))
print(-1 * reduce(lambda a, b: a + b, arr))

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
A = list(map(int, input().split()))

import heapq

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

for _ in range(m):
    tmp = heapq.heappop(A)/2
    heapq.heappush(A, tmp)
    
ans = 0
for a in A:
    ans += -int(a)
print(ans)

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

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

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

print(-sum(arr))

Solution (Python):
from heapq import heapify, heapreplace

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

for _ in range(m):
    heapreplace(arr, int(arr[0] / 2))

print(-sum(arr))

Solution (Python):
import heapq as hp
n,m=[int(x) for x in input().rstrip().split()]
a=[-int(x) for x in input().rstrip().split()]

hp.heapify(a)
a.sort()

while(m):
  
  m-=1
  now=hp.heappop(a)
  now=-((-now)//2)
  hp.heappush(a,now)
  
print(-sum(a))

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

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 = [int(x) for x in input().split()]
A.sort(reverse=True)
A = list(map(lambda x: x*-1,A))
heapq.heapify(A)
while(m>0):
    m-=1
    num = heapq.heappop(A)
    if(num == 0):
        break
    num //= (-2)
    heapq.heappush(A,num*-1)

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

Solution (Python):
n, m  = map(int, input().split())
import numpy as np
import heapq
import math
a = [-1*int(i) for i in input().split()]
heapq.heapify(a)

if n > 1:
  for i in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a,math.ceil(x/2))
  a = np.array(a)
  print(-1*a.sum())
else:
  print(-1*a[0]//(2**m))

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

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)







from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
h=[-i for i in A]
heapify(h)

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

B=[int(-i) for i in h]
print(sum(B))

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)







from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
h=[-i for i in A]
heapify(h)

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

B=[int(-i) for i in h]
print(sum(B))

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M = rl()
A = rl()

import heapq

heap = []
for i, a in enumerate(A):
	heapq.heappush(heap, (-a, i))
nums = [0] * N
for i in range(M):
	a, i = heapq.heappop(heap)
	if abs(a) < 1:
		break
	a = a / 2
	nums[i] += 1
	heapq.heappush(heap, (a, i))
ans = 0
for i in range(N):
	ans += A[i] // pow(2, nums[i])
print(ans)

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

Solution (Python):
import heapq
import math

def calc(n):
    return n*(-1)

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    AA = list(map(calc, A)) 
    heapq.heapify(AA) 
    
    for i in range(M):
        tmp = heapq.heappop(AA)
        tmp = math.floor(-tmp / 2)*(-1)
        heapq.heappush(AA, tmp)
    
    print(sum(AA)*(-1))

main()

Solution (Python):
import heapq 
n,m = map(int,input().split())
l = list(map(int,input().split()))
l1 = [-i for i in l]
heapq.heapify(l1)

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

Solution (Python):
def main():
    import heapq
    n, m, *a = map(lambda x: -int(x), open(0).read().split())
    heapq.heapify(a)
    for _ in range(-m):
        x = heapq.heappop(a)
        heapq.heappush(a, x / 2)

    ans = -sum(map(lambda x: int(x), a))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import heapq
    n, m, *a = map(lambda x: -int(x), open(0).read().split())
    heapq.heapify(a)
    while m:
        x = heapq.heappop(a)
        heapq.heappush(a, x / 2)
        m += 1
    ans = -sum(map(lambda x: int(x), a))
    print(ans)
    


if __name__ == '__main__':
    main()

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 _ in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A, (-x//2)*(-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_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(int, input().split()))
ans = 0

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

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

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

import heapq
heapq.heapify(A)

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

print(-sum(A))

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

Solution (Python):
import heapq

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

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

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

print(-sum(pA))

Solution (Python):
n,m = map(int,input().split())
a = list(map(int,input().split()))
q = []
for i in a:
    q.append(-i)

import heapq
heapq.heapify(q)

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

print(-sum(q))

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):
    val = heapq.heappop(a) * (-1)
    heapq.heappush(a, (val // 2) * (-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)

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 = [-1 * int(a) for a in 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):
n,m = map(int,input().split())
import math
a_list = list(map(int,input().split()))
for i in range(n):
  a_list[i] = -1 * a_list[i]
import heapq
heapq.heapify(a_list)
for j in range(m):
  
  a = heapq.heappop(a_list)
  a = math.ceil(a/2)
  heapq.heappush(a_list,a)


print(-1 * sum(a_list))

Solution (Python):
import heapq

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

heapq.heapify(A)

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

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

Solution (Python):
import heapq

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

while M > 0:
    M -= 1
    now = heapq.heappop(B)
    now = (now+1) // 2
    heapq.heappush(B, now)
print(-sum(B))

Solution (Python):
from heapq import heappop, heappush

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

H = []

for i in A:
  heappush(H, i)

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

print((-1)*sum(H))

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()))
A=[-i for i in A]

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

Solution (Python):

def main():
    import sys
    import heapq as hp
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(lambda x:-int(x), sys.stdin.readline().split()))
    A.sort()
    hp.heapify(A)
    
    while M>0:
        tmp = hp.heappop(A) 
        tmp = -((-tmp)//2)
        hp.heappush(A, tmp)
        M-=1
    print(-sum(A))
   
if __name__=='__main__':
    main()

Solution (Python):

from collections import deque
import bisect
import math

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


if len(A_list) > 1:
    A_list.sort(reverse=False)
    highest = A_list.pop()
    next_highest = A_list[-1]

    discounted_deque = deque()

    while 1:
        use_tickets = math.ceil(math.log(highest/next_highest)/math.log(2))
        if use_tickets == 0:
            use_tickets = 1
        elif use_tickets > M:
            use_tickets = M
            
        highest /= pow(2,use_tickets)
        M -= use_tickets
        
        if M!= 0:
            discounted_deque.appendleft(highest)
            
            if len(A_list) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    highest = A_list.pop()
                else:
                    highest = discounted_deque.pop()
            else:
                highest = discounted_deque.pop()
                
            if len(A_list) > 0 and len(discounted_deque) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    next_highest = A_list[-1]
                else:
                    next_highest = discounted_deque[-1]
            elif len(A_list) == 0 and len(discounted_deque) > 0:
                next_highest = discounted_deque[-1]
            elif len(A_list) > 0 and len(discounted_deque) == 0:
                next_highest = A_list[-1]
            
        else:
            A_list.append(highest)
            break

    A_list = [int(A) for A in A_list]
    discounted_list = [int(B) for B in discounted_deque]
    
    print(sum(A_list)+sum(discounted_list))
else:
    A_list[-1] = A_list[-1]//(pow(2,M))
    print(A_list[-1])

Solution (Python):
from math import ceil
from heapq import heappush, heappop, heapify
N, M = map(int, input().split())
A_i = list(map(lambda x: -int(x), input().split()))
heapify(A_i)

for _ in range(M):
    heappush(A_i, ceil(heappop(A_i) / 2))

print(-sum(A_i))

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

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

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

print(-sum(a))

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

while M>0:
    A.sort(reverse=True)
    if A[0]==0:
        break
    judge=A[0]//2
    for i in range(len(A)):
        if A[i]>judge and M>0:
            A[i]=A[i]//2
            M-=1
        else:
            break
print(sum(A))

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()

A = [-x for x in A]
heapify(A)

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

print(-sum(A))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()

A = [-x for x in A]
A.sort()

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

print(-sum(A))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()

A = [-x for x in A]
A.sort()

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

print(-sum(A))

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

Solution (Python):
import queue

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

q = queue.PriorityQueue()
for a in A:
    q.put((-a,a))

for _ in range(M):
    v = q.get()[1] // 2
    q.put((-v, v))

ans = 0
while not q.empty():
    ans += q.get()[1]
print(ans)

Solution (Python):
import sys


import math
import collections



import fractions

import copy
import heapq
import decimal

import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

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





def main():
    n, m = ns()
    a = [-int(i) for i in input().split()]
    heapq.heapify(a)

    cnt = 0
    while cnt < m:
        cnt += 1

        item = heapq.heappop(a)
        item = (item + 1) // 2
        heapq.heappush(a, item)

    ans = 0
    while len(a) > 0:
        ans += - heapq.heappop(a)

    print(ans)


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 _ in range(M):
    m = heapq.heappop(A)
    
    heapq.heappush(A, -(-m // 2))
    

print(-sum(A))

Solution (Python):
from heapq import heapify, heappush, heappop
class PriorityQueue():
    def __init__(self, queue=[]):
        self.queue = queue
        heapify(queue)
    def push(self, item):
        heappush(self.queue, item)
    def pop(self):
        return heappop(self.queue)
    def __str__(self):
        return self.queue
    def __len__(self):
        return len(self.queue)
    def __iter__(self):
        return iter(self.queue)
N, M = map(int, input().split())
def int_(num_str):
    return -int(num_str)


Alist = list(map(int_, input().split()))
pq = PriorityQueue(Alist)
for _ in range(M):
    max_val = pq.pop()
    pq.push(-1 * (-1*(max_val))/2)
ans = sum([int(-1 * item) for item in pq])
print(ans)

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):
    MAX = heapq.heappop(a)  
    heapq.heappush(a, (-1) * (-MAX // 2))

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

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

Solution (Python):
import sys
from io import StringIO
import unittest
import heapq

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,m=map(int, readline().rstrip().split())
    arr=list(map(int, readline().rstrip().split()))
    for i in range(n):
        arr[i]*=-1
    heapq.heapify(arr)
    for _ in range(m):
        x=(heapq.heappop(arr)*-1)//2
        heapq.heappush(arr, -x)
    ans=0
    for i in range(n):
        ans+=(arr[i]*-1)
    print(ans)
    
    
    

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

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

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

PQ = [-A for A in As]
heapify(PQ)

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



print(-sum(PQ))

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

from heapq import heappop,heappush,heapify

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

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

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

from heapq import heappop,heappush,heapify

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

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

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

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

print(-sum(dat))

Solution (Python):
import heapq

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

heapq.heapify(a)


for i in range(m):
  maxa = heapq.heappop(a)
  heapq.heappush(a, maxa/2)
  
ans = 0
for i in range(n):
  ans += int(heapq.heappop(a))
  
print(-ans)