Problem:
 Score : 400 points    Problem Statement Takahashi is going to buy N items one by one.  The price of the i -th item he buys is A_i yen (the currency of Japan).  He has M discount tickets, and he can use any number of them when buying an item.  If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.  What is the minimum amount of money required to buy all the items?      Constraints  All values in input are integers.  1 \leq N, M \leq 10^5  1 \leq A_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  M  A_1  A_2  ...  A_N       Output Print the minimum amount of money required to buy all the items.        Sample Input 1 3 3
2 13 8      Sample Output 1 9  We can buy all the items for 9 yen, as follows:   Buy the 1 -st item for 2 yen without tickets.  Buy the 2 -nd item for 3 yen with 2 tickets.  Buy the 3 -rd item for 4 yen with 1 ticket.        Sample Input 2 4 4
1 9 3 5      Sample Output 2 6       Sample Input 3 1 100000
1000000000      Sample Output 3 0  We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.       Sample Input 4 10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 4 9500000000

Solution (Python):

from heapq import heapify, heappop, heappush


def main():
    N, M, *A = map(int, open(0).read().split())
    H = [-i for i in A]
    heapify(H)
    replace = lambda: heappush(H, -(-heappop(H) // 2))
    for _ in range(M):
        replace()
    ans = -sum(H)
    print(ans)


if __name__ == "__main__":
    main()

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)

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

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

Solution (Python):
import heapq
def f(str):
    return -int(str)

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

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

print(-sum(A))

Solution (Python):

N, M = map(int,input().split())
A = list(-int(i) for i in input().split())
import heapq

heapq.heapify(A)
for _ in range(M):
    a = heapq.heappop(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, A))
heapq.heapify(A)

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

print(-sum(A))

Solution (Python):

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

queue = []
for a in A:
    heappush(queue, -a)
    
for _ in range(M):
    tmp = heappop(queue)
    heappush(queue, int(tmp / 2))
    
ans = 0
for _ in range(N):
    ans -= heappop(queue)
    
print(ans)

Solution (Python):
class heap():
    def __init__(self, maxcom=True):
        if maxcom:
            self.compare = lambda x, y: x > y
        else:
            self.compare = lambda x, y: x < y

    def heappush(self, x, heap):
        heap.append(x)
        length = len(heap)
        pointer = length
        while True:
            if pointer == 1:
                break
            if self.compare(heap[pointer - 1], heap[(pointer >> 1) - 1]):
                heap[pointer - 1], heap[(pointer >> 1) - 1] = heap[(pointer >> 1) - 1], heap[pointer - 1]
                pointer = pointer >> 1
            else:
                break

    def heapreplace(self, function, heap):
        heap[0] = function(heap[0])
        pointer = 1
        length = len(heap)
        while True:
            if (pointer << 1) > length:
                break
            elif (pointer << 1) + 1 > length :
                if self.compare(heap[(pointer << 1) - 1], heap[pointer - 1]):
                    heap[(pointer << 1) - 1], heap[pointer - 1] = heap[pointer - 1], heap[(pointer << 1) - 1]
                else:
                    break
            else:
                if self.compare(heap[(pointer << 1) - 1], heap[pointer << 1]):
                    next_pointer = pointer << 1
                else:
                    next_pointer = (pointer << 1) + 1
                if self.compare(heap[next_pointer - 1], heap[pointer - 1]):
                    heap[next_pointer - 1], heap[pointer - 1] = heap[pointer - 1], heap[next_pointer - 1]
                    pointer=next_pointer
                else:
                    break


n, m = map(int, input().split())
a = map(int, input().split())
heapq = []
heapc=heap(True)
for i in a:
    heapc.heappush(i,heapq)
for _ in range(m):
    heapc.heapreplace(lambda x:x>>1,heapq)
print(sum(heapq))

Solution (Python):
import heapq

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



A = [-i for i in A]

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


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

n, m = map(int,input().split())
q = Heapq(list(map(int,input().split())),True)
for i in range(m):
    q.push(q.pop()//2)
ans = 0
for i in range(n):
    ans += q.pop()
print(ans)

Solution (Python):
from sys import stdin
import heapq
N,M = [int(x) for x in stdin.readline().rstrip().split()]
A = [-int(x) for x in stdin.readline().rstrip().split()]
heapq.heapify(A)
for _ in range(M):
    v = -heapq.heappop(A)
    v //= 2
    heapq.heappush(A,-v)
ans = -sum(A)
print(ans)

Solution (Python):
import heapq

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

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

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

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

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

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

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


prices = [ -p for p in map(int, input().split(' ')) ]
heapify(prices)

for _ in range(m):
    p = heappop(prices)
    heappush(prices, p / 2)

total = 0
while prices:
    total += math.floor(-heappop(prices))
print(total)

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

print(-sum(q))

Solution (Python):
import heapq

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

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

print(-1 * sum(A))

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

obj = input().strip().split(' ')
N, M = map(int, obj)

obj = input().strip().split(' ')
val_list = [-1 * item for item in list(map(int, obj))]

heapify(val_list)

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

print(-1 * sum(val_list))

Solution (Python):
import heapq
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):
    heapq.heappush(A,heapq.heappop(A)/2)
for i in range(N):
    A[i]=-1*int(A[i])
print(sum(A))

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

print(-sum(q))

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

print(-sum(q))

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

print(-sum(q))

Solution (Python):
import heapq
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):
    q=heapq.heappop(A)
    q=q/2
    heapq.heappush(A,q)
for i in range(N):
    A[i]=-1*int(A[i])
print(sum(A))

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






max_heap = [a[0]]

def add_heap(array, number):
    array.append(number)

    def swap(array, number, idx):
        if idx == 1:
            return array[idx-1]

        ai = array[idx-1]
        target_idx = (idx//2)
        target = array[target_idx-1]
        
        if ai >= target:
            array[idx-1], array[target_idx-1] =  target, ai

            number = swap(array, number, target_idx)
        else:
            return array[idx-1]

    return swap(array, number, len(array))



for ai in a[1:]:
    add_heap(max_heap, ai)


for _ in range(m):
    
    
    max_heap[0] //= 2
    
    def sort_heap(array, number, idx):
        top = number
        left_idx = idx*2
        right_idx = idx*2 + 1
        
        if left_idx > len(array):
            left = -1
        else:
            left = array[left_idx - 1]

        if right_idx > len(array):
            right = -1
        else:        
            right = array[right_idx - 1]

        if top >= left and top >= right:
            return array
        elif left > right:
            array[idx-1], array[left_idx-1] = left, top
            sort_heap(array, top, left_idx)
        else:
            array[idx-1], array[right_idx-1] = right, top
            sort_heap(array, top, right_idx)

    sort_heap(max_heap, max_heap[0], 1)


print(sum(max_heap))

Solution (Python):
import math
import heapq

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

hq = []
for i in range(n):
  heapq.heappush(hq, a[i]*(-1))

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

ans = 0
for i in hq:
  ans += i *(-1)
print(ans)

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

Solution (Python):
import heapq

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



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

print(-sum(L))

Solution (Python):

import heapq

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

pq = []

for i in data:
    heapq.heappush(pq, -i)

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

print(-sum(pq))

Solution (Python):

import heapq

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

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





heapq.heapify(a)


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

print(-1 * sum(a))

Solution (Python):
import heapq	

n,m=map(int,input().split())
a=list(map(int,input().split()))
hq=[]
for i in range(len(a)):
  heapq.heappush(hq,-a[i])

if n==1:
  for i in range(m):
    hq[0]=(((-1)*hq[0])//2)*(-1)
else:
  for i in range(m):
    v=heapq.heappop(hq)
    heapq.heappush(hq,((v*-1)//2)*(-1))

ans=0
for i in range(len(hq)):
  ans=ans+(-1)*heapq.heappop(hq)

print(ans)

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

list1 = list(map(int,input().split()))
list1.sort()
list1.reverse()
i = 0
s = math.floor(list1[0]/2)
 
if n == 1:
    print(math.floor(list1[0]/(2**m)))
    exit()
 
while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m == 0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))

Solution (Python):
import sys
import heapq as hq
input = sys.stdin.readline
N, M = list(map(int,input().strip().split()))
A = list(map(int,input().strip().split()))
A = list(map(lambda x:-x, A))
hq.heapify(A)
for i in range(M):
	target = A[0]/2
	hq.heappushpop(A,target)
A = list(map(lambda x:-x, A))
print(sum(map(int,A)))

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

test = [0]*N

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

import heapq

heapq.heapify(A)

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

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

Solution (Python):
import heapq

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

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

Solution (Python):
from bisect import bisect_left
 
N,M = map(int, input().split())
A = sorted([int(x) for x in input().split()])
 
while M > 0:
    x = A.pop(-1)
    x //= 2
    ind = bisect_left(A, x)
    M -= 1
    if ind < N-1:
        temp = [x] + [A[-i-1]//2 for i in range(min(M, N-1 - ind))]
        A = sorted(A[:N-len(temp)] + temp)
    else:
        A.insert(bisect_left(A, x), x)
    M -= N-1 - ind
 
print(sum(A))

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

l = len(A)

if N>=2:
  while M>=1:
    A.sort(reverse=True)
    div = A[0]//2
    
    for i in range(l):
      if A[i]>=div:
        if M>=1:
          A[i] = A[i]//2
          M -= 1
        else:
          break
      else:
        break
 
  print(sum(A))
else:
    i=1
    while 2**(i+1)<=A[0]:
      i+=1
    if M>=i:
      print(0)
    else:
      print(A[0]//2**M)

Solution (Python):
import heapq

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

q = []
heapq.heapify(q)

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

for i in range(n):
    heapq.heappush(q, - a[i])

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

ans = 0
for i in range(n):
    v = - heapq.heappop(q)
    ans += v
print(ans)

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

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

Solution (Python):

import heapq
n, m = [int(x) for x in input().split()]
h = [-int(x) for x in input().split()]
heapq.heapify(h)
for i in range(m):
    x = heapq.heappop(h)
    heapq.heappush(h, -(-x//2))
z = 0
print(-sum(h))

Solution (Python):

import heapq
n, m = [int(x) for x in input().split()]
h = [-int(x) for x in input().split()]
heapq.heapify(h)
for i in range(m):
    x = heapq.heappop(h)
    heapq.heappush(h, -(-x//2))
z = 0
print(-sum(h))

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

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

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

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

heapq.heapify(A)

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

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

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

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

print(-sum(A_minus))

Solution (Python):
import heapq as hq

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

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

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

    
print(-1*sum(arr))

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

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

Solution (Python):
import heapq
import numpy as np

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

a.sort()
a = np.array(a)
a = -1 * a
a = list(a)
heapq.heapify(a)

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

print(-1 * sum(a))

Solution (Python):

import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")

from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import nlargest
from heapq import nsmallest


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

H = list( -int(i) for i in input().split() )


p("H ",H)

heapify(H)

p("H ",H)

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


print(-sum(H))

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

Solution (Python):
n,m = map(int,input().split())
arr = list(map(int,input().split()))
l = len(arr)

while m != 0 :
    arr.sort(reverse=True)
    j = arr[0] // 2
    for i in range(l):
            if arr[i] > j:
                if m != 0:
                    m -= 1
                else:
                    break
                arr[i] //= 2
            else:
                break
    if arr[0] == 0:
        break
            

print(sum(arr))

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


heapq.heapify(A)
 


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

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

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

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

h = []

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

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

print(-sum(h))

Solution (Python):

import heapq as hq
def main():
    N,M = map(int,input().split())
    A=[-int(j) for j in input().split()]
    hq.heapify(A)
    for _ in range(M):
        tmp = hq.heappop(A)
        hq.heappush(A,(-((-tmp)//2)))
    print(-sum(A))
if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush,heappop
N,M=input().split(" ")
N=int(N)
M=int(M)
Alist=input().split(" ")

hAqueue=[]
for A in Alist:
    heappush(hAqueue,-float(A))

for m in range(M):
    tmp=heappop(hAqueue)
    heappush(hAqueue,tmp/2)
Alist = [-int(A) for A in hAqueue]
print(sum(Alist))

Solution (Python):
import heapq
 
L1 = input().split(" ")
L2 = input().split(" ")
tickets = int(L1[1])
L2int = [-int(s) for s in L2]
 
heapq.heapify(L2int)
 
for t in range(tickets):
    heapq.heappush(L2int,-(-heapq.heappop(L2int)//2))
print(-sum(L2int))

Solution (Python):
import heapq

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

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

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





print(sum(A)*-1)

Solution (Python):
import heapq


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


itemCount, ticketCount = map(int, input().split(' '))
prices = map(int, input().split(' '))

h = []
for price in prices:
    _heappush_max(h, price)

for i in range(ticketCount):
    price = _heappop_max(h)
    _heappush_max(h, price // 2)
total = 0
for price in h:
    total += price

print(total)

Solution (Python):
import sys,heapq,math
sys.setrecursionlimit(100000)

def ins(): return input().split()
def ii(): return int(input())
def iil(): return list(map(int,ins()))
def lin(): return list(input())
def iin(): return map(int,ins())

n,m=iin()
a=list(map(lambda x:-int(x),ins()))
heapq.heapify(a)
tmp = heapq.heappop(a)
for i in range(m):
    tmp = heapq.heappushpop(a,math.ceil(tmp/2))
print(-(sum(a)+tmp))

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

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

res = M
while res > 0:
    a = heapq.heappop(pque)
    a = -(abs(a) >> 1)
    heapq.heappush(pque, a)
    res -= 1
print(-sum(int(x) for x in pque))

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

Solution (Python):
from heapq import*;n,m,*a=map(lambda x:-int(x),open(0).read().split());heapify(a);exec("heappush(a,0-heappop(a)//-2);"*-m);print(-sum(a))

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

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

b = copy.deepcopy(a)
heapq.heapify(b)

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

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

print(sum(b)*-1)

Solution (Python):
from sys import stdin
import heapq


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    As = []
    for i in [int(x) for x in stdin.readline().rstrip().split()]:
        heapq.heappush(As, -i)
    for _ in range(M):
        x = heapq.heappop(As)
        heapq.heappush(As, -(-x // 2))
    print(sum([-1 * x for x in As]))


if __name__ == "__main__":
    main()

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

a = input()
list1 = list(map(int,a.split()))
list1.sort()
list1.reverse()
i = 0
s = math.floor(list1[0]/2)

if n == 1:
    print(math.floor(list1[0]/(2**m)))
    exit()

while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m == 0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))

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

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

heapq.heapify(A)

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

print(-sum(A))

Solution (Python):
import sys
inputs = sys.stdin.readlines()

import heapq
from heapq import heapify, heappush, heappop, _heapify_max
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    lastelt = heap.pop()
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

N, M = map(int, inputs[0].split())
A = list(map(int, inputs[1].split()))
_heapify_max(A)
for _ in range(M):
    _heappush_max(A, _heappop_max(A) // 2)
print(sum(A))

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

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

Solution (Python):
import heapq

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

a = [- int(i) for i in input().split(" ")]
heapq.heapify(a)

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

print(- sum(a))

Solution (Python):
import heapq

n, m = map(int, input().split())
prices = [-int(p) for p in input().split()]
heapq.heapify(prices)
for _ in range(m):
  p = heapq.heappop(prices)
  heapq.heappush(prices, p / 2)
print(-sum(int(p) for p in prices))

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

Solution (Python):
N, M = [int(nm) for nm in input().split()]
A = [int(a) for a in input().split()]
A.sort(reverse = True)

while M >= 1:
  A[0] //= 2
  M -= 1
  
  i = 1
  while True:
    if N >= i*2 + 1:
      A1, A2, A3 = A[i-1], A[i*2 - 1], A[i*2]
    elif N == i*2:
      A1, A2, A3 = A[i-1], A[i*2 - 1], 0
    else:
      A1, A2, A3 = A[i-1], 0, 0

    if A1 < A2 or A1 < A3:
      if A2 >= A3:
        A[i-1], A[i*2 - 1] = A2, A1
        i = i*2
      else:
        A[i-1], A[i*2] = A3, A1
        i = i*2 + 1
    else:
      break

ans = sum(A)
print(ans)

Solution (Python):
import heapq
import math

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

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

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

b = []
for hqi in hq:
  b.append(hqi * -1)
  
print(sum(b))

Solution (Python):
import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
q = []
for x in A:
    heapq.heappush(q, -x)
for m in range(M):
    x = heapq.heappop(q)
    x /= 2
    heapq.heappush(q, x)
ans = 0
for x in q:
    ans += int(-x)
print(ans)

Solution (Python):
import heapq, math

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

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

print(-sum(a))

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

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

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

Solution (Python):
import heapq

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

Solution (Python):

import sys
import heapq

def solve(N: int, M: int, A: "List[int]"):
    A = [-a for a in A]
    heapq.heapify(A)
    for m in range(M):
        largest = -1 * heapq.heappop(A)
        largest = int(largest / 2)
        heapq.heappush(A, -1 * largest)

    print(-1 * sum(A))
    return

def solve_slow(N: int, M: int, A: "List[int]"):
    """
    遅い実行
    """
    A = sorted(A, reverse=True)
    m = 0
    while m < M:
        m += 1
        A[0] = A[0] // 2
        while m < M and len(A) > m and A[0] > A[M-m-1]:
            m += 1
            A[0] = A[0] // 2

        if (len(A) >= 2) and (A[0] < A[1]):
            tmp = A[0]
            A = A[1:]
            for i, a in enumerate(A):
                if a <= tmp:
                    A.insert(i, tmp)
                    break
                if i == len(A)-1:
                    A.insert(len(A)-1, tmp)
                    break
    print(sum(A))
    return





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

if __name__ == '__main__':
    main()

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


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

import heapq

heapq.heapify(lista)

for i in range(m):
        b=heapq.heappop(lista)
        b=b/2
        heapq.heappush(lista,b)
        
for i in range(n):
        lista[i]=int(lista[i]*-1)

ans=sum(lista)
print(ans)

Solution (Python):
import heapq
def _heappush_max(heap,item):
  heap.append(item)
  heapq._siftdown_max(heap,0,len(heap)-1)
def _heappop_max(heap):
  lastelt=heap.pop()
  if heap:
    returnitem=heap[0]
    heap[0]=lastelt
    heapq._siftup_max(heap,0)
    return returnitem
  return lastelt

n,m=map(int,input().split())
a=list(map(int,input().split()))
heapq._heapify_max(a)
for i in range(m):
    _heappush_max(a,_heappop_max(a)//2)
print(sum(a))

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

Solution (Python):
from sys import stdin
import heapq
n, m = map(int, stdin.readline().rstrip().split())
ary = list(map(int, stdin.readline().rstrip().split()))

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


heapq._heapify_max(ary)

for i in range(m):
    temp = _heappop_max(ary) // 2
    _heappush_max(ary, temp)

res = sum([heapq.heappop(ary) for _ in range(n)])
print(res)