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):
N, M = map(int, input().rstrip().split())
S = list(map(int, input().rstrip().split()))
S = [-x for x in S]
import heapq
heapq.heapify(S)

for i in range(M):
    val = int(heapq.heappop(S) / 2)
    heapq.heappush(S, val)
print(-sum(S))

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

Solution (Python):
from heapq import heappush, heappop
import numpy as np

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

price = [int(x) for x in input().split()] 
hq_price = []
for p in price:
  heappush(hq_price, -p)

for m in range(M):
  max_tmp = heappop(hq_price)
  heappush(hq_price, max_tmp/2.)

price = [int(-x) for x in hq_price]
print(sum(price))

Solution (Python):
import heapq

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

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

heapq.heapify(nums)

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

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

Solution (Python):
import heapq

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

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

heapq.heapify(nums)

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

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

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()))
a = list(map(lambda x: x*(-1), a))


heapq.heapify(a)

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

ans = 0
for num in a:
    ans += int(-num)

print(ans)

Solution (Python):
import heapq

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

Solution (Python):
import heapq

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

a = [-int(n) for n in input().split()]

heapq.heapify(a)

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

print(-sum(a))

"""
for i in range(m):
    a.sort()
    a.reverse()
    m -= 1
    a[0] = a[0] // 2

print(sum(a))
"""
"""
def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]
"""

Solution (Python):
import heapq

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

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

Solution (Python):
import heapq

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

H = []
for a in map(int, input().split()):
    heapq.heappush(H, -a)

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

print(-1 * sum(H))

Solution (Python):

import heapq

n, m = map(int, input().split())
l = [ -1 * int(n) for n in input().split()]

heapq.heapify(l)

for i in range(m):
    a = heapq.heappop(l) * (-1)
    a = int(a/2)
    if a != 0:
        heapq.heappush(l, a * (-1))
    if len(l) == 0:
        break
    
    
print(sum(l) * (-1))

Solution (Python):
import math
import heapq


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



itemCount = i[0]

discountTicketsCount = i[1]


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





priceList = [ n * -1 for n in priceList]
heapq.heapify(priceList)


for i in  range(discountTicketsCount):

    
    target = abs(heapq.heappop(priceList))

    
    target = math.floor(target / 2)

    
    heapq.heappush(priceList, target * -1)


print(abs(sum(priceList)))

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

Solution (Python):
import heapq

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

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

for i in range(m):
    ai = heapq.heappop(h)
    heapq.heappush(h, -(-ai//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):
    temp = heapq.heappop(A) * (-1)
    heapq.heappush(A, (-1)*(temp // 2))


print(-sum(A))

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

npA = []
for x in a:
    heapq.heappush(npA, -x)



npA.sort()


for x in range(M):
    
    
    heapq.heappush(npA, math.ceil(heapq.heappop(npA)/2))
    

total = 0
for x in range(N):
    
    
    total+=heapq.heappop(npA)

print(-total)

Solution (Python):
import heapq

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

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

Solution (Python):


import heapq
import math

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

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

heapq.heapify(A)


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

print(-sum(A))

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

decimal.getcontext().prec = 20



def solve(f):
    n, m = f.read_int_list()
    a = f.read_int_list()

    h = []
    for ai in a:
        heapq.heappush(h, -decimal.Decimal(ai))

    two = decimal.Decimal(-2)
    for i in xrange(m):
        item = -heapq.heappop(h)
        heapq.heappush(h, item/two)

    ans = 0
    for hi in h:
        ans += int(-hi)

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

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 i in range(M):
    heapq.heappush(A, heapq.heappop(A)/2)
print(sum(map(lambda x: int(-x), A)))

Solution (Python):
import heapq

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

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

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

Solution (Python):
from bisect import bisect_right
import heapq
n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselists=[]
for _ in lists:
    uselists.append(-_)

heapq.heapify(uselists)

cnt=0
while cnt<m:
    y=heapq.heappop(uselists)

    z=(-y)//2
    heapq.heappush(uselists,-z)
    

    cnt+=1
anslist=[]
for j in uselists:
    anslist.append(-j)
print(sum(anslist))

Solution (Python):
import heapq
X = list(map(int, input().split()))

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

for i in range(X[1]):
  x = heapq.heappop(A) * (-1) 
  heapq.heappush(A, int(x/2) * (-1))

ans = 0
for i in range(X[0]):
  ans -= A[i]

print(ans)

Solution (Python):
import heapq

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

ans = 0

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

for i in range(N):
    ans -= A_heap[i]

print(ans)

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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    d = {"Sunny":1 , "Cloudy":2, "Rainy":0}
    a = ["Sunny", "Cloudy", "Rainy"]
    print(a[d[input().rstrip()]])
    return


def B():
    s = S()
    for i, si in enumerate(s):
        if i % 2:
            if si == "R":
                print("No")
                return
        else:
            if si == "L":
                print("No")
                return
    print("Yes")
    return


def C():
    n, k, q = LI()
    d = [0] * n
    for _ in range(q):
        a = II() - 1
        d[a] += 1
    for a in d:
        if k - (q - a) > 0:
            print("Yes")
        else:
            print("No")
    return


def D():
    n,m = LI()
    a = LI()
    q = []
    for ai in a:
        heappush(q, -ai)
    for _ in range(m):
        heappush(q, heappop(q) / 2)
    ans = 0
    while q:
        ans += int(-heappop(q))
    print(ans)
    return


def E():
    return


def F():
    return


if __name__ == '__main__':
    D()

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

sum = 0
for _ in range(N): 
	sum -= heapq.heappop(h)
print(sum)

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

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

A = list(map(int, input().split()))
h = []

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

for i in range(N):
    heapq.heappush(h, A[i])

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

print(-sum(h))

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

Solution (Python):

 
import heapq
 
N, M = map(int, input().split())
invA = []
for a in map(int, input().split()):
    heapq.heappush(invA, -1*a)
for m in range(M):
    heapq.heappush(invA, heapq.heappop(invA)/2)
total = -1*sum(map(int, invA))
 
print(total)

Solution (Python):


import heapq

N, M = map(int, input().split())
invA = []
for a in map(int, input().split()):
    heapq.heappush(invA, -1*a)
for m in range(M):
    heapq.heappush(invA, heapq.heappop(invA)/2)
total = -1*sum(map(int, invA))

print(total)

Solution (Python):






from sys import stdin,setrecursionlimit

import heapq



setrecursionlimit(10**6)
input=stdin.readline

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

heapq.heapify(a)
for _ in range(m):
    now=-heapq.heappop(a)
    now//=2
    heapq.heappush(a,-now)
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):
    tmp_min = heapq.heappop(A)
    heapq.heappush(A,int(tmp_min / 2))
    
print(-sum(A))

Solution (Python):

import heapq

MOD = 10 ** 9 + 7

N, M = map(int, input().split())
AN = map(int, input().split())
hq = []
for an in AN:
    heapq.heappush(hq, -an)

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

ans = - sum(hq)

print(ans)

Solution (Python):
import heapq

N, M =map(int, input().split())
A = list(map(int, input().split()))
A.sort()
reversed_A = [n * (-1) for n in A]
heapq.heapify(reversed_A)
for i in range(M):
    max_value = heapq.heappop(reversed_A) * (-1)
    half_value = max_value // 2
    heapq.heappush(reversed_A, (-1)*half_value)

discount_prices = [n * (-1) for n in reversed_A]
ans = sum(discount_prices)
print(ans)

Solution (Python):

import heapq
n,m = map(int, input().split())
price = list(map(int, input().split()))
for i in range(n):
    price[i] = -price[i]
heapq.heapify(price)

for i in range(m):
    x = heapq.heappop(price)
    if x%2 == 0:
        heapq.heappush(price,x//2)
    else:
        heapq.heappush(price,x//2+1)
print(-sum(price))

Solution (Python):
import heapq as hq


def solve():
    N, M = map(int, input().split())
    pl = list(map(lambda x: int(x)*(-1), input().split()))
    hq.heapify(pl)
    
    for _ in range(M):
        tmp = hq.heappop(pl)
        hq.heappush(pl, (-1)*(-tmp // 2))
    
    print(-sum(pl))
    


if __name__ == '__main__':
    solve()

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):
    heapq.heappush(A, ((heapq.heappop(A) * -1) >> 1) * -1)

print(sum(A) * -1)

Solution (Python):

from heapq import heappop, heappush

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

heap = []
for i in input().split():
    heappush(heap, -int(i))

for i in range(M):
    a = -heappop(heap)
    half = a // 2
    heappush(heap, -half)
    
ans = -sum(heap)
print(ans)

Solution (Python):
import heapq

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

heapq.heapify(A_list)

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

print(sum(A_list) * -1)

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):
from heapq import heappush, heappop
 
N, M = map(int, input().split())
 
goods = list(map(int, input().split()))
goods_heap = []
 
for i in range(N):
    heappush(goods_heap, -goods[i])
 
for _ in range(M):
    heappush(goods_heap, -(-heappop(goods_heap)//2))
    
sum = -sum(goods_heap)
 
print(sum)

Solution (Python):
import heapq
l = list()
n,m = map(int,input().split())
a_l = list(map(int,input().split()))
for x in a_l:
    x *= -1
    heapq.heappush(l,x)
for _ in range(m):
    y = heapq.heappop(l)*(-1)
    y = y//2
    heapq.heappush(l,(-1)*y)
print((-1)*sum(l))

Solution (Python):
import heapq
import math
def main():
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  c=[-i for i in c]
  heapq.heapify(c)
    
  for j in range(b):
    x=heapq.heappop(c)
    heapq.heappush(c,math.ceil(x/2))
    
  print(-sum(c))
  
if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import math
n,m = map(int,input().split())
lst = [int(x) * (-1) for x in input().split()]
heapq.heapify(lst)
for use_cnt in range(m):
    num = heapq.heappop(lst) * -1
    nxt_num = math.floor(num / 2)
    heapq.heappush(lst,nxt_num * -1)
print(sum(lst) * (-1))

Solution (Python):
import heapq
import math
n,m = map(int,input().split())
lst = [int(x) * (-1) for x in input().split()]
heapq.heapify(lst)
for use_cnt in range(m):
    num = heapq.heappop(lst) * -1
    nxt_num = math.floor(num / 2)
    heapq.heappush(lst,nxt_num * -1)
print(sum(lst) * (-1))

Solution (Python):
import heapq

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

cost=[]
heapq.heapify(cost)

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

min_cost=sum(A)

while M>0:
    max_cost=(-1)*heapq.heappop(cost)
    cut_cost=max_cost-max_cost//2
    min_cost-=cut_cost
    max_cost-=cut_cost
    heapq.heappush(cost,(-1)*max_cost)
    M-=1

print(min_cost)

Solution (Python):

import heapq
def main():
    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))
if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

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

goods = list(map(int, input().split()))
goods_heap = []

for i in range(N):
    heappush(goods_heap, -goods[i])

for _ in range(M):
    heappush(goods_heap, -(-heappop(goods_heap)//2))
    
sum = -sum(goods_heap)

print(sum)

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

Solution (Python):
import heapq

n,m=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
for i in range(n):
  heapq.heappush(q,-arr[i])
for _ in range(m):
  tmp=-heapq.heappop(q)
  heapq.heappush(q,-(tmp//2))
ans=0
for _ in range(n):
  ans+=-heapq.heappop(q)
print(ans)

Solution (Python):
import heapq
import math


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


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


for use_count in range(m):
    
    max_price = heapq.heappop(price_list) * -1
    
    
    new_price = math.floor(max_price / 2)
    
    
    heapq.heappush(price_list, new_price * -1)


print(sum(price_list) * -1)

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

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [-a for a in A]
heapq.heapify(B)
for _ in range(M):
    v = heapq.heappop(B)
    v = -(abs(v)//2)
    heapq.heappush(B, v)
print(-sum(B))

Solution (Python):
import heapq

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

d = list(map(lambda x: -x, data))
heapq.heapify(d)

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

d = list(map(lambda x: -x, d))

print( sum(d) )

Solution (Python):
class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

inpl = lambda: list(map(int,input().split()))

if __name__ == '__main__':
    N, M = inpl()
    A = inpl()
    segt = SegmentTree(A, reverse=True)
    for _ in range(M):
        i = segt.query_index()
        v = segt.at(i)
        segt.update(i, v//2)
    print(sum(segt.at(i) for i in range(N)))

Solution (Python):
import heapq

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

N, M = map(int, input().split())
values = list(map(int, input().split()))
tmp = 0

values_minus = []
for val1 in values:
    values_minus.append(calc_minus(val1))

heapq.heapify(values_minus)

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

values_plus = []
for val2 in values_minus:
    values_plus.append(calc_minus(val2))

result = 0
for val3 in values_plus:
    result += val3

print(result)

Solution (Python):
import heapq

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

Solution (Python):
import heapq

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
h = []
for a in A:
    heapq.heappush(h, -a)

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

print(-sum([heapq.heappop(h) for x in range(len(h))]))

Solution (Python):
import heapq
import math

n, m = map(int, input().split())
goods = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(goods)
for i in range(m):
    the_most_expensive = heapq.heappop(goods)
    heapq.heappush(goods, math.ceil(the_most_expensive / 2))

print(sum(goods) * -1)

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

Solution (Python):
import heapq

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

Solution (Python):
import sys
n,m = map(int,input().split())
lst_a = list(map(int,input().split()))
temp = 0
cnt = 0
loop = 0
debug = 0
if n == 1:
    for i in range(m):
        lst_a[0] //= 2
    print(lst_a[0])
    sys.exit()
while debug < 10:
    loop = 0
    temp = 0
    lst_a.sort(reverse=True)
    while loop < n-1:
        lst_a[loop] //= 2
        cnt += 1
        temp = max(temp,lst_a[loop])
        if cnt == m:
            print(sum(lst_a))
            sys.exit()
        if temp > max(lst_a[loop],lst_a[loop + 1]):
            break
        if lst_a[loop + 1] > lst_a[loop]:
            loop += 1

Solution (Python):
import sys
n,m = map(int,input().split())
lst_a = list(map(int,input().split()))
temp = 0
cnt = 0
fin = 0
loop = 0
debug = 0
temp2 = 0
if n == 1:
    for i in range(m):
        lst_a[0] //= 2
    print(lst_a[0])
    sys.exit()
while debug < 10:
    loop = 0
    
    temp = 0
    lst_a.sort(reverse=True)
    while loop < n-1:
        lst_a[loop] //= 2
        cnt += 1
        temp = max(temp,lst_a[loop])
        if cnt == m:
            
            print(sum(lst_a))
            sys.exit()
        if temp > max(lst_a[loop],lst_a[loop + 1]):
            break
        if lst_a[loop + 1] > lst_a[loop]:
            loop += 1
        
        
        
"""        if lst_a[loop] >= max(lst_a[loop + 1],temp):
            lst_a[loop] //= 2
            temp = max(lst_a[loop],lst_a[loop+1])
            cnt += 1
            if cnt == m:
                print(sum(lst_a))
                sys.exit()
            if temp > lst_a[loop + 1]:
                break
            
            
        loop += 1
    
    
print(lst_a[99999])




"""

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


if __name__ == '__main__':
    slove()

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

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

Solution (Python):
def main():
    from heapq import heapify, heappush, heappop
    from math import floor
    n, m = list(map(int, input().split(' ')))
    a = list(map(int, input().split(' ')))
    a = [x*(-1) for x in a]
    heapify(a)
    for _ in range(m):
        x = floor(-heappop(a)/2)*(-1)
        heappush(a, x)
     
    print(-sum(a))
main()

Solution (Python):
def main():
    from heapq import heapify, heappush, heappop
    from math import floor
    n, m = list(map(int, input().split(' ')))
    a = list(map(int, input().split(' ')))
    a = [x*(-1) for x in a]
    heapify(a)
    for _ in range(m):
        x = floor(-heappop(a)/2)*(-1)
        heappush(a, x)
     
    print(-sum(a))
main()

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

def intm(x):
    return int(x)*-1
A = list(map(intm, input().split()))

import heapq

heapq.heapify(A)
while M>0:
    a = -heapq.heappop(A) // 2
    heapq.heappush(A,-a)
    M -= 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)

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

print(-sum(A))

Solution (Python):
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): 
    N,M =map(int,input().split())
    A = list(map(int,input().split()))
    heap = []
    for i in range(N):
        heappush(heap,-A[i])
    for i in range(M):
        p = -heappop(heap)//2
        heappush(heap,-p)
    print(-sum(heap))
    
if __name__ == "__main__":
    main()

Solution (Python):
import heapq as h

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

Solution (Python):
import heapq

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

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

print(-sum(a))

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

heapq.heapify(b)
for i in range(m):
    h = heapq.heappop(b)
    heapq.heappush(b, math.ceil(h / 2))

print(sum(b)*(-1))

Solution (Python):
import heapq
import math

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

heapq.heapify(b)
for i in range(m):
    h = heapq.heappop(b)
    heapq.heappush(b, math.ceil(h / 2))

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

print(sum(c))