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 heapq
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

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

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

Solution (Python):
from heapq import heapify, heapreplace

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

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

for _ in range(M):
    heapreplace(A, -(-A[0]//2))
print(-sum(A))

Solution (Python):
import copy
import heapq

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)

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


n,m = ips()
a = iprow()
a.sort(reverse=True)

heapq._heapify_max(a)
b = _heappop_max(a)
_heappush_max(a, b)
for i in range(m):
    b = _heappop_max(a)
    
    b//=2
    _heappush_max(a,b)
print(sum(a))

Solution (Python):
import copy
import heapq

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)

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


n,m = ips()
a = iprow()
a.sort(reverse=True)

heapq._heapify_max(a)
for i in range(m):
    b = _heappop_max(a)
    
    b//=2
    _heappush_max(a,b)
print(sum(a))

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

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

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


print(-sum(B))

Solution (Python):

import sys
import heapq


class Reverse:
    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        return self.val > other.val

    def __repr__(self):
        return repr(self.val)


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        if self.desc:
            return heapq.heappop(self.hq).val
        else:
            return heapq.heappop(self.hq)

    def push(self, a):
        if self.desc:
            heapq.heappush(self.hq, Reverse(a))
        else:
            heapq.heappush(self.hq, a)

    def top(self):
        if self.desc:
            self.hq[0].val
        else:
            return self.hq[0]


def solve(N: int, M: int, A: "List[int]"):
    hq = Heapq(A, desc=True)
    while M > 0:
        MD = hq.pop()
        M -= 1
        hq.push((MD//2))
        if MD <= 0:
            break
    ans = 0
    while A:
        a = hq.pop()
        ans += a
    print(ans)
    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())

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

list.sort(A, reverse=True)

while M>0:
    A[0] = int(A[0] / 2)
    
    M -= 1
    if M==0:
        break
    for i in range(1,N):
        if(A[i] > A[0]):
            A[i] = int(A[i] / 2)
            
            M -= 1
            if M == 0:
                break
        else:
            break
    list.sort(A, reverse=True)


print(sum(A))

Solution (Python):
from heapq import heapify, heapreplace
n,m = map(int,input().split())
L = [  -i for i in map(int, input().split())]
heapify(L)
for _ in range(m):
    heapreplace(L,L[0]//2 + L[0]%2)
print(-sum(L))

Solution (Python):

import sys


def solve(N: int, M: int, A: "List[int]"):
    while M > 0:
        A = sorted(A, reverse=True)
        MD = A[0] // 2
        for i, ai in enumerate(A):
            if ai > MD and M > 0:
                A[i] = ai//2
                M -= 1
            else:
                break
        if A[i] == 0:
            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())
A = list(map(int, input().split()))

while M>0:
  A = sorted(A, reverse=True)
  a_ = A[0]//2
  for i,a_i in enumerate(A):
    if a_i > a_ and M>0:
      A[i] = a_i//2
      M -= 1
    else: break
  if a_==0: break
print(sum(A))

Solution (Python):
import heapq

n, m = map(int, input().split())
a = [-int(_) for _ in input().split()]

heapq.heapify(a)

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

res_list = [int(-_) for _ in a]
print(sum(res_list))

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

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

print(-sum(lis))

Solution (Python):

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

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

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

import heapq
a = [-1*i for i in a]
heapq.heapify(a)
for i in range(M):
    b = heapq.heappop(a)
    b = (-1*b)//2
    heapq.heappush(a, -1*b)
print(-1*sum(a))

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappop, heappush

n, m = li()
a = list(li())

heap = []

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

for _ in range(m):
    bi = -heappop(heap)
    heappush(heap, -(bi//2))

print(-sum(heap))

Solution (Python):
import heapq as hq

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

B = [-i for i in A]
hq.heapify(B)
for i in range(M):
    x = hq.heappop(B)
    hq.heappush(B, -(-x//2))
print(-1*sum(B))

Solution (Python):
import heapq

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

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

print(-1*sum(A))

Solution (Python):
import heapq

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

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

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

Solution (Python):
from heapq import heappush, heappop

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

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

sumi = 0
while True:
	try:
		sumi += (-1 * heappop(pq))
	except Exception as e:
		break;
print(sumi)

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

a = sorted(a)

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

print(-1*sum(a))

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

Solution (Python):
'''
Created on 2019/09/28

@author: oiwaiman
'''

import heapq as hq

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [-i for i in A]
hq.heapify(B)
for i in range(M):
    a_largest = int((-B[0])/2)
    a_list = hq.heappushpop(B, -a_largest)

sum = 0
for j in range(N):
    sum -= B[j]

print(sum)

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

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

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

ans = 0
for a in A:
    ans -= int(a)

print(ans)

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

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

import heapq
heapq.heapify(A)

for ticket_num in range(1,M+1):
    max_value = -1*heapq.heappop(A)
    heapq.heappush(A, -1*(max_value>>1))

print(-1*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 _ 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_array = map(int, input().split())

h = []
for a in A_array:
    heapq.heappush(h, -a)

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

ans = 0
for i in range(N):
    p = heapq.heappop(h)
    ans += int(-p)

print(ans)

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

while M>0:
    max_a = heapq.heappop(A)
    heapq.heappush(A,-int(-max_a/2))
    M = 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 i in range(m):
	target = heapq.heappop(a)
	heapq.heappush(a, (-1)*(-target//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):
	target = heapq.heappop(a)
	heapq.heappush(a, (-1)*(-target//2))
	
print(-sum(a))

Solution (Python):
from heapq import *
N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapify(A)
for x in range(M):
    tmp = int(heappop(A)/2)
    heappush(A,tmp)
res = 0
for x in A:
    res -= x
print(res)

Solution (Python):
def main():
    import sys,heapq,math
    input = sys.stdin.readline

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

    tank = []
    for e in a:
        heapq.heappush(tank,-e)
    
    for i in range(m):
        heapq.heappush(tank,heapq.heappop(tank)/2.0)

    res = 0
    for e in tank:
        res += math.floor(-e)
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline
class SkewHeap:
  def __init__(self, init_val = None):
    self.val = init_val
    self.left = None
    self.right = None
    self.root = None
  def heapmeld(self, h1, h2):
    if h1 == None: return h2
    if h2 == None: return h1
    if h1.val > h2.val:
      h1.val, h1.left, h1.right, h2.val, h2.left, h2.right = h2.val, h2.left, h2.right, h1.val, h1.left, h1.right
    h1.right = self.heapmeld(h2, h1.right)
    h1.left, h1.right = h1.right, h1.left
    return h1
  def heappop(self):
    res = self.root.val
    self.root = self.heapmeld(self.root.left, self.root.right)
    return res
  def heappush(self, x):
    h = SkewHeap(x)
    self.root = self.heapmeld(self.root, h)
  def heaptop(self):
    return self.root.val
N, M = map(int, input().split())
a = list(map(int, input().split()))
h = SkewHeap()
res = 0
for e in a:
  h.heappush(-e)
for _ in range(M):
  h.heappush(-(-h.heappop() // 2))
for _ in range(N):
  res -= h.heappop()
print(res)

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

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

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

Solution (Python):
import heapq

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

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

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

heapq.heapify(A)

def chaep(n):
    n=int(n/2)
    return  n
i=0
while(i<M):
    tmp=heapq.heappop(A)
    tmp=chaep(tmp)
    heapq.heappush(A,tmp)
    i+=1

print(-sum(A))

Solution (Python):
import heapq

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

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

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

heapq.heapify(A)

def chaep(n):
    n=int(n/2)
    return  n
i=0
while(i<M):
    tmp=heapq.heappop(A)
    tmp=chaep(tmp)
    heapq.heappush(A,tmp)
    i+=1

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

print(ans*(-1))

Solution (Python):
import heapq

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

heapq.heapify(A)

ans=0
def cheap(x,y):
    x=int(x/(2**y))
    return x

i=0
while(i<M):
    tmp=heapq.heappop(A)
    tmp=cheap(tmp,1)
    heapq.heappush(A,tmp)
    i+=1

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

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

Solution (Python):

"""
Created on Thu Oct  3 07:43:37 2019

@author: avina
"""

import heapq

class Maxheap():
    
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)
    
    def push(self, value):
        heapq.heappush(self.heap, -value)
    
    def pop(self):
        return -heapq.heappop(self.heap)

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

l = list(map(int, input().split()))
a = Maxheap(l)
for i in range(t):
    b = a.pop()//2
    a.push(b)
    
sums = 0
for i in range(n):
    sums += a.pop()
print(sums)

Solution (Python):

"""
Created on Wed Oct  2 07:56:16 2019

@author: avina
"""
from queue import PriorityQueue as Q
n,t = map(int,input().split())

q = Q()
for i in input().split():
    a = -1*int(i)
    q.put(a)

while t >0:
    a = -1*(q.get())
    a = -1*(a//2)
    q.put(a)
    t-=1

ans = 0
while q.qsize()>0:
    ans += q.get()
print(-1*ans)

Solution (Python):

import heapq


class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)

    def push(self, value):
        heapq.heappush(self.heap, -value)

    def pop(self):
        return -heapq.heappop(self.heap)

N, M = list(map(lambda x:int(x), input().split(' ')))
l = list(map(lambda x:int(x), input().split(' ')))

maxheap = MaxHeap(l)

WARI = 0.5
for _ in range(0, M):
    v = int(maxheap.pop() * WARI)
    maxheap.push(v)

SUM = 0
for _ in range(0, N):
    SUM += maxheap.pop()

print(SUM)

Solution (Python):







import math
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):
    max_A = heapq.heappop(A)
    max_A = max_A * -1
    heapq.heappush(A,-1* (math.floor((max_A) / 2)) )

print(-1 * sum(A))

Solution (Python):


import math
import heapq

goods, tickets = map(int, input().split())

price = []
price = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(price)


for i in range(tickets):
    max = heapq.heappop(price) * (-1)
    heapq.heappush(price, math.ceil(-max/2))
   

total = 0
for i in range(goods):
    total += price[i]

print(total * (-1))

Solution (Python):
import heapq

N, M = map(int, input().split())
values = list(map(int, input().split()))
sortedValues = []

for v in values:
    heapq.heappush(sortedValues, (-1)*v)

for i in range(M):
    heapq.heappush(sortedValues, int((heapq.heappop(sortedValues) * 1/2)))

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

Solution (Python):
import heapq as hq
N,M = map(int,input().split())
A = [-int(i) for i in input().split()]
hq.heapify(A)
for i in range(M):
    x = hq.heappop(A)
    x = -(-x>>1)
    hq.heappush(A,x)
print(sum([-i for i 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)
    heapq.heappush(a, (-x//2)*(-1))

print(-sum(a))

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

pque = []

for i in A:
    heapq.heappush(pque, -i)

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

print (-sum(pque))

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

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

Solution (Python):
import sys
from io import StringIO
import unittest
import heapq
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
2 13 8"""
        output = """9"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4 4
1 9 3 5"""
        output = """6"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1 100000
1000000000"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000"""
        output = """9500000000"""
        self.assertIO(input, output)
def resolve():
    (n,m)=(int(i) for i in input().split())
    A=[int(i) for i in input().split()]
    q=[]
    for i in A:
        heapq.heappush(q,-i)
    for i in range(m):
        x=q[0]
        heapq.heappushpop(q,int(x/2))
    print(-sum(q))
if __name__ == "__main__":
    resolve()

Solution (Python):
import heapq

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

Solution (Python):

from heapq import heapify, heappop, heappush
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
item_list = [int(x) * (-1) for x in input().split()]

heapify(item_list)

for i in range(M):
    price = heappop(item_list)
    price = int(price / 2)
    heappush(item_list, price)

total = -sum(item_list)
print(total)

Solution (Python):
import heapq



n, m = list(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 sys
import heapq

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

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

h = [(1/a, a) for a in A]
heapq.heapify(h)

for m in range(M):
    x = heapq.heappop(h)
    _, a = x

    a //= 2

    heapq.heappush(h, (1/a if a > 0 else float('inf'), a))

print(sum([a for _, a in h]))

Solution (Python):
import heapq
import math

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

Solution (Python):
import heapq

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

heapq.heapify(h)

for _ in range(M):
    min_value = heapq.heappop(h)
    heapq.heappush(h, min_value / 2)

print(sum(map(lambda x: -1 * int(x), h)))

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

import heapq
class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)
    def push(self, value):
        heapq.heappush(self.heap, -value)
    def pop(self):
        return -heapq.heappop(self.heap)
    def sum(self):
        return -sum(self.heap)

a = MaxHeap(a)

for i in range(m):
    largest = a.pop()
    a.push(largest//2)
print(a.sum())

Solution (Python):

import sys
import math
import numpy as np
import heapq
from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False


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



heapq.heapify(A)


def discount(num_coupon):
  max = -heapq.heappop(A) / 2
  heapq.heappush(A, -max)



for i in range(0, M):
  max = math.floor(-heapq.heappop(A) / 2)
  heapq.heappush(A, -max)

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

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

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


item.sort(reverse=True)


while m != 0:
    
    
    for i in range(n):
        
        
        if i == 0:
            item[i] = int(item[i]/2)
            m -= 1
            temp = item[i]
            if m == 0:
                break
            continue
        
        
        if item[i] > temp:
            item[i] = int(item[i]/2)
            m -= 1
            if m == 0:
                break
            continue
        
        
        item.sort(reverse=True)
        break


print(sum(item))

Solution (Python):
import heapq

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

for _ in range(m):
  v = heapq.heappop(a)
  o = v % 2
  v /= 2
  heapq.heappush(a, v + o)

print(-1*sum(a))

Solution (Python):
import heapq
N,M=map(int,input().split())
A=tuple(map(int,input().split()))
l=[(-i,i) for i in A]
heapq.heapify(l)
for _ in range(M):
    m=heapq.heappop(l)
    heapq.heappush(l,(-(m[1]//2),m[1]//2))
a=0
for i in l:
    a+=i[1]
print(a)

Solution (Python):
import heapq
N,M=map(int,input().split())
A=tuple(map(int,input().split()))
l=[(-i,i) for i in A]
heapq.heapify(l)
for _ in range(M):
    m=heapq.heappop(l)
    heapq.heappush(l,(-(m[1]//2),m[1]//2))
a=0
for i in l:
    a+=i[1]
print(a)

Solution (Python):
import heapq

n, m = map(int, input().split())
a_list = []
for i in input().split(): heapq.heappush(a_list, -int(i))

for x in range(m):
	tmp = heapq.heappop(a_list) / 2
	heapq.heappush(a_list, tmp)

print(sum([int(-x // 1) for x in a_list]))

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

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

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

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

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

Solution (Python):
import heapq


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

for i in range(m):
    minus_max = alist[0]
    heapq.heapreplace(alist, ((-1)*minus_max >> 1)*(-1))

print(-1*sum(alist))

Solution (Python):
import heapq


class MaxHeap:
    def __init__(self, H=[]):
        self.heapify(H)

    def heapify(self, H):
        self._neg_heap = [ -a for a in H ] 
        heapq.heapify( self._neg_heap )

    def push(self, value):
        heapq.heappush(self._neg_heap, -value)

    def pop(self):
        return (-1) * heapq.heappop(self._neg_heap)

    def get_heap(self):
        return [ -a for a in self._neg_heap ]






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

price_heap = MaxHeap(A)

i = 0
for i in range(M):
    price = price_heap.pop() 
    price //= 2  
    price_heap.push(price) 
    i += 1

total_price = 0
new_prices = price_heap.get_heap()

for i in range(N):
    total_price += new_prices[i]

print(total_price)

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

Solution (Python):
import queue
MAXIMUM = 10 ** 10
q = queue.PriorityQueue()
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
for a in A:
  q.put((-a, a))

while M > 0:
  item = q.get()
  if item[1] == 0:
    break
  q.put((-int(item[1]/2), int(item[1]/2)))
  M -= 1

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

Solution (Python):
import heapq

def receive_shopping_plan():
    num_commodity, num_coupon = input().split(' ')
    num_commodity, num_coupon = int(num_commodity), int(num_coupon)
    return num_commodity, num_coupon

def calc_minimized_sum(num_commodity, num_coupon):
    prices = list(map(lambda x: int(x) * -1 , input().split(' ')))
    heapq.heapify(prices)
    for _ in range(num_coupon):
        max_price = heapq.heappop(prices) // (2*-1)
        heapq.heappush(prices, max_price*-1)

    print(sum(prices)*-1)

if __name__ == '__main__':
    num_commodity, num_coupon = receive_shopping_plan()
    calc_minimized_sum(num_commodity, num_coupon)

Solution (Python):
from heapq import heappop, heappush


def main():
    N, M = map(int, input().split())
    lst_A = list(map(int, input().split()))

    pqueue = []
    for A in lst_A:
        heappush(pqueue, -A)

    for m in range(M):
        a = heappop(pqueue)
        a *= -1
        a //= 2
        a *= -1
        heappush(pqueue, a)
    ans = -sum(pqueue)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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

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

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

print(-sum(hq))

Solution (Python):
import heapq
N,M=map(int,input().split())
lst=list(map(int,input().split()))
A=[]
for i in range(N):
  heapq.heappush(A,-1*lst[i])
while M!=0:
  val=heapq.heappop(A)
  M-=1
  new_val=val/2
  heapq.heappush(A,new_val)

ans=0
for i in range(N):
  ans+=-1*int(A[i])
print(ans)