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



Sample input:
3 3
2 13 8


Sample output:
9

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
import numpy as np
from functools import lru_cache

args = sys.argv
if len(args) == 2:
  import IPython

def embed():
  if len(args) == 2:
    sys.stdin = open('/dev/tty')
    IPython.embed()

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

#### functions
def discount(price_list, num_coupon):
  if num_coupon == 0:
    return price_list
  else:
    if len(price_list) == 1:
      price_list[0] = math.floor(price_list[0]  / 2** num_coupon)
      return price_list
    else:
      sorted_list = sorted(price_list)
      max1st = sorted_list[-1]
      max2nd = sorted_list[-2]
      num_div = min(num_coupon, math.floor(math.log2(max1st / max2nd)) + 1)
      max_i = np.argmax(price_list)
      price_list[max_i] = math.floor(price_list[max_i] / 2**num_div)
      price_list = discount(price_list, num_coupon - num_div)
      return price_list

print(sum(discount(A, M)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
import numpy as np
from functools import lru_cache

args = sys.argv
if len(args) == 2:
  import IPython

def embed():
  if len(args) == 2:
    sys.stdin = open('/dev/tty')
    IPython.embed()

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

#### functions
discount_dic = {}

def discount(price_list, num_coupon):
  if num_coupon == 0:
    return price_list
  else:
    if len(price_list) == 1:
      price_list[0] = math.floor(price_list[0]  / 2** num_coupon)
      return price_list
    else:
      sorted_list = sorted(price_list)
      dic_key = "_".join(map(str, sorted_list))
      if dic_key in discount_dic:
        return discount_dic[dic_key]
      else:
        max1st = sorted_list[-1]
        max2nd = sorted_list[-2]
        num_div = min(num_coupon, math.floor(math.log2(max1st / max2nd)) + 1)
        max_i = np.argmax(price_list)
        price_list[max_i] = math.floor(price_list[max_i] / 2**num_div)
        price_list = discount(price_list, num_coupon - num_div)
        discount_dic[dic_key] = price_list
        return price_list

print(sum(discount(A, M)))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lis=list(map(int,input().split()))
cost=0
for i in range (0,n):
  cost=cost+lis[i]
lis.sort()
discount=0
for i in range (0,m):
  a=0
  b=n-1
  discount=discount+lis[n-1]-lis[n-1]//2
  t=lis[n-1]//2
  for i in range (0,4):
    if lis[(a+b)//2]<t:
      a=(a+b)//2
    elif lis[(a+b)//2]>t:
      b=(a+b)//2
    else:
      a=b=(a+b)//2
  while lis[a]<t and a<n:
    a=a+1
  lis.insert(a,t)
  del lis[n]
  print(lis)
print(cost-discount)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
t=0
while True:
  maxi=A[0]
  if len(A)>1 :
    maxi_2=A[1]
    t+=1
    maxi=maxi//2
    if t==M :
      A[0]=maxi
      break
    elif maxi_2>maxi :
      A[0]=maxi_2
      A[1]=maxi
      for i in range(1,N):
        if A[i]<A[i+1]:
          A[i]=A[i+1]
          A[i+1]=maxi
        else:
          break     
      continue
    else:
      continue
  else :
    maxi=maxi//(2**M)
    A[0]=maxi
    break

amount=sum(A)
print(amount)

Submission status: Runtime Error

Solution code:
import queue
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((-item[1]//2, item[1]//2))
  M -= 1

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

for i in range(M):
  prices[0]=prices[0]//2
  if N>1:
    if prices[0] < prices[1]:
      temp = prices[0]
      for j in range(M):
        if prices[j] < temp:
          break
      for k in range(j-1):
        prices[k] = prices[k+1]
      prices[j-1] = temp

total=0
for i in range(N):
  total += int(prices[i])
print(total)

Submission status: Runtime Error

Solution code:
import numpy as np

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

for i in range(M):
  prices[0]=prices[0]//2
  if prices[0] < prices[1]:
    temp = prices[0]
    for j in range(M):
      if prices[j] < temp:
        break
    for k in range(j-1):
      prices[k] = prices[k+1]
    prices[j-1] = temp

total=0
for i in range(N):
  total += int(prices[i])
print(total)

Submission status: Runtime Error

Solution code:
import numpy as np

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

for i in range(M):
  prices[0]=prices[0]//2
  if prices[0] < prices[1]:
    temp = prices[0]
    for j in range(M):
      if prices[j] < temp:
        break
    for k in range(j):
      prices[k] = prices[k+1]
    prices[j] = temp

total=0
for i in range(N):
  total += int(prices[i])
print(total)

Submission status: Runtime Error

Solution code:
import heapq

# 入力の取得(1行目。数値)
i = list(map(int, input().split()))

# 変数セット
# 1.購入する品物の数
itemCount = i[0]
# 2.割引券の数
discountTicketsCount = i[1]

# 入力の取得(2行目。数値)
priceList = list(map(int, input().split()))

# 「符号反転した」リストを優先度付きキューに変換
# ★ポイント★
# heapqは最小値しか取り出せないため、
# 符号反転してからキューに変換=>最小値を取る、という手法を行う。
priceList = [ n * -1 for n in priceList]
heapq.heapify(priceList)

# キューから最小値の取り出し
aaa = heapq.heappop(priceList)
print(aaa)
aaa = heapq.heappop(priceList)
print(aaa)


# 合計金額を出力
# print(sum(priceList))

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
A = []
for X in input().split():
	x = int(X)
	A.append(x)

for x in range(M):
	max = A.index(max(A))
	A[max] = A[max] / 2

sum = 0
for x in range(len(A)):
	sum += int(A[x])

print(sum)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right

n,m=map(int,input().split())
lis=list(map(int,input().split()))
lists=sorted(lis)

cnt=0
while cnt<m:
    y=lists[-1]//2
    del lists[-1]
    
    indexes=bisect_left(lists,y)
    #indexesというところに新しいyの値を代入しておきたい
    lists.insert(indexes,y)

    cnt+=1
print(sum(lists))

Submission status: Runtime Error

Solution code:
(N,M) = list(map(int,input().split()))
Aorg = list(map(int,input().split()))


A = Aorg.sort(reverse=True)[M]

sumA = sum(Aorg)

for m in range(M):
  #print(A.index(max(A)))
  sumA = int(sumA - max(A)/2)
  A[A.index(max(A))] = int(A[A.index(max(A))] - max(A)/2)

print(sum(A))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
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')

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

#B
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

#C
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

#D
def D():
    n, = 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

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
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')

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

#B
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

#C
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

#D
def D():
    n, = 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

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Runtime Error

Solution code:
import math

n,m = map(int,input().split())
while True:
    try:
        listA=list(map(int,input().split()))
    except:
        break;
sum=0
l=1
listA.sort()
for i in range(m):
  if listA[n-1-i]>listA[n-l]:
    listA[n-1-i]=math.floor(listA[n-1-i]/2)
  elif i==0:
    listA[n-1-i]=math.floor(listA[n-1-i]/2)
  else:
    listA[n-l]=math.floor(listA[n-l]/2)
    if listA[n-l]<listA[n-l-1]:
      l+=1
#  print(listA[0],listA[1],listA[2],l)
for i in range(n):
  sum+=listA[i]

print(sum)

Submission status: Runtime Error

Solution code:
import math

n,m = map(int,input().split())
while True:
    try:
        listA=list(map(int,input().split()))
    except:
        break;
sum=0
l=1
listA.sort()
for i in range(m):
  if listA[n-1-i]>listA[n-l]:
    listA[n-1-i]=math.floor(listA[n-1-i]/2)
  else:
    listA[n-l]=math.floor(listA[n-l]/2)
    if listA[n-l]<listA[n-l-1]:
      l+=1
for i in range(n):
  sum+=listA[i]

print(sum)

Submission status: Runtime Error

Solution code:
import math

n,m = map(int,input().split())
while True:
    try:
        listA=list(map(int,input().split()))
    except:
        break;
sum=0
listA.sort()
for i in range(m):
  listA[n-1]=math.floor(listA[n-1]/2)
  for j in range(m):
    if listA[n-1-j]<listA[n-2-j]:
      listA[n-1-j],listA[n-2-j]=listA[n-2-j],listA[n-1-j]
    else:
      break
for i in range(n):
  sum+=listA[i]

print(sum)

Submission status: Runtime Error

Solution code:
import math

n,m = map(int,input().split())
while True:
    try:
        listA=list(map(int,input().split()))
    except:
        break;
sum=0
listA.sort()
for i in range(m):
  listA[n-1]=math.floor(listA[n-1]/2)
  for j in range(m)
  if listA[n-1-j]<listA[n-2-j]:
    listA[n-1-j],listA[n-2-j]=listA[n-2-j],listA[n-1-j]
  else:
    break
for i in range(n):
  sum+=listA[i]

print(sum)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
while True:
    try:
        listA=list(map(int,input().split()))
    except:
        break;

for i in range(m):
  Alist.sort()
  Alist[n-1]=Alist[n-1]/2

for i in range(n):
  sum=0
  sum+=Alist[i]

print(sum)

Submission status: Runtime Error

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

for _ in range(M):
	a = A.pop()
	a //= 2
	for i in A:
		if i > a:
			A.insert(A.index(i), a)
			break

sum = 0
for a in A: sum += a
print(sum)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
t=0
while True:
  maxi=A[0]
  maxi_2=A[1]
  t+=1
  maxi=maxi//2
  if t==M :
    A[0]=maxi
    break
  elif maxi_2>maxi :
    A[0]=maxi
    A.sort(reverse=True)
    continue
  else:
    continue

amount=sum(A)
print(amount)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
t=0
while True:
  maxi=A[0]
  maxi_2=A[1]
  t+=1
  maxi=maxi//2
  if t==M :
    A[0]=maxi
    break
  elif maxi_2>maxi :
    A[0]=maxi_2
    A[1]=maxi
    continue
  else:
    continue

amount=sum(A)
print(amount)

Submission status: Runtime Error

Solution code:
N,M=map(int,input.split())
A=list(map(int,input().split()))
A.sort(reverse=True)
t=0
while True:
  maxi=A[0]
  maxi_2=A[1]
  t+=1
  maxi=maxi//2
  if t==M :
    A[0]=maxi
    break
  elif maxi_2>maxi :
    A[0]=maxi_2
    A[1]=maxi
    continue
  else:
    continue

amount=sum(A)
print(amount)

Submission status: Runtime Error

Solution code:
import heapq
N, M = list(map(int,input()))
h = []
for x in input().split():
  heappush(h, x)
print(heappop(h))
print(heappop(h))

Submission status: Runtime Error

Solution code:
n,m=[int(x) for x in input().split()]
v=[int(x) for x in input().split()]
def insert(list, n): 
      
    for i in range(len(list)): 
        if list[i] > n: 
            break
      
    list = list[:i] + [n] + list[i:] 
    return list
v.sort()
while (m>0):
	k=v[-1]/2
	del v[-1]
	v=insert(v,k)
	m-=1
i,sum=0,0
print(v)
while(i<n):
	sum+=int(v[i])
	i+=1
print(sum)

Submission status: Runtime Error

Solution code:
n,m=[int(x) for x in input().split()]
v=[int(x) for x in input().split()]
def insert(list, n): 
      
    for i in range(len(list)): 
        if list[i] > n: 
            break
      
    list = list[:i] + [n] + list[i:] 
    return list
v.sort()
while (m>0):
	k=v[0]/2
	del v[0]
	v=insert(v,k)
	m-=1
i,sum=0,0
while(i<n):
	sum+=int(v[i])
	i+=1
print(sum)

Submission status: Runtime Error

Solution code:
import bisect

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

A_list = sorted(A_list)
#print(A_list)

for i in range(M):
    val = A_list.pop()//2
    bisect.insort_left(A_list, val, lo=(N-M) + i )

print(sum(A_list))

Submission status: Runtime Error

Solution code:
# -*-coding: utf-8 -*-
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()

Submission status: Runtime Error

Solution code:
# -*-coding: utf-8 -*-
import numpy as np

N, M = map(int, input().split())
A = list(map(int, input().split()))
np_A = np.array(A)
for i in range(M):
    num = np_A.argmax()
    np_A[num] //= 2

print(sum(np_A))

Submission status: Runtime Error

Solution code:
import heapq

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

print(sum(goods) * -1)

Submission status: Runtime Error

Solution code:
import heapq

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

print(sum(goods) * -1)

Submission status: Runtime Error

Solution code:
import heapq

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

print(sum(goods) * -1)

Submission status: Runtime Error

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

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

import heapq
def heapsort(iter):
    h = []
    for value in iter:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

def waribiki(X,Y):
    return X//(2**Y)

if len(A)==1:
    while M>0:
        A[0] = waribiki(A[0],1)
        M -= 1
else:
    while M>0:
        #A.sort(reverse=True)
        A = heapsort(A)
        
        m=1
        #while M>0 and waribiki(A[0],m)>A[1]:
        #    m+=1
        A[0] = waribiki(A[0],m)
        M -= m
       

print(sum(A))

Submission status: Runtime Error

Solution code:
/*
         ██╗ ██████╗ ██╗███╗   ██╗    ██╗   ██╗███████╗
         ██║██╔═══██╗██║████╗  ██║    ██║   ██║██╔════╝
         ██║██║   ██║██║██╔██╗ ██║    ██║   ██║███████╗
    ██   ██║██║   ██║██║██║╚██╗██║    ██║   ██║╚════██║
    ╚█████╔╝╚██████╔╝██║██║ ╚████║    ╚██████╔╝███████║
     ╚════╝  ╚═════╝ ╚═╝╚═╝  ╚═══╝     ╚═════╝ ╚══════╝
*/
//password:+BdCHpO8dQvpo5fnV3/u
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;
priority_queue<ll>pq;

int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        pq.push(x);
    }
    while(m--)
    {
        ll r=pq.top();
        pq.pop();
        r/=2;
        pq.push(r);
    }
    ll ans=0;
    while(pq.size()) ans+=pq.top(),pq.pop();
    cout<<ans<<endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
n, m, *a = map(int, open(0).read().split())
new_a = sorted(a, reverse=True)
sum = 0
length = len(new_a)
if length >= m:
    for pirce in new_a[m:]:
        sum += price
    new_a = new_a[:m]
    length = len(new_a)
    for _ in range(m, 0, -1):
        if new_a[0] < 1:
            break
        new_a[0] /= 2
        new_a.sort(reverse=True)
        sum += int(new_a[-1])
        new_a = new_a[:-1]
else:
    for i in range(m, 0, -1):
        if new_a[0] < 1:
            break
    new_a[0] /= 2
    new_a.sort(reverse=True)
    if length >= i:
        sum += int(new_a[-1])
        new_a = new_a[:-1]
for price in new_a:
    sum += int(price)
print(sum)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(M):
  big = max(A)
  A[A.index(A)] = 2 / big
  ans += big 
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import collections
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A = collections.deque(A)
for i in range(M):
  B = A.pop()
  bisect.insort_left(A,B//2)
print(sum(A))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
N, K = list(map(int, input().split()))

Alist = [int(i) for i in input().split(' ')]
import math

Alist=sorted(Alist, reverse=True)

Blist=[]

def insert_list(list, value):
	start=0
	end=len(list)-1

	if value<list[len(list)-1]:
		list.insert(len(list), value)
		return list
	if value>list[0]:
		list.insert(0, value)
		return list
	while True:
		mid_point=int((start+end)/2)
		if value>list[mid_point]:
			if (end-start)<2:
				list.insert(start, value)
				return list
			else:
				end=mid_point
		else:
			if (end-start)<2:
				list.insert(end, value)
				return list
			else:
				start=mid_point

for i in range(K):
   if N==1:
      Alist[0]=Alist[0]/2**K
      break
   #Alist[0]=Alist[0]/2
  
   if len(Blist)==0:
      Blist.append(Alist.pop(0))
      Blist[0]=Blist[0]/2
   else:
      if Blist[0]>Alist[0]:
         Blist[0]=Blist[0]/2
         Blist=insert_list(Blist,Blist.pop(0))
      else:
         Blist.insert(0, Alist.pop(0))
         Blist[0]=Blist[0]/2
         Blist=insert_list(Blist,Blist.pop(0))
sum=0

for i in Alist:
   sum+=math.floor(i) 
    
for i in Blist:
   sum+=math.floor(i) 
print(int(sum))

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))

Alist = [int(i) for i in input().split(' ')]
import math

#print(Alist)
my_list = [9,8,7,4,7,1,3]

Alist=sorted(Alist, reverse=True)

def insert_list(list, value):
	start=0
	end=len(list)-1

	if value<list[len(list)-1]:
		list.insert(len(list), value)
		return list
	if value>list[0]:
		list.insert(0, value)
		return list
	while True:
		mid_point=int((start+end)/2)
		if value>list[mid_point]:
			if (end-start)<2:
				list.insert(start, value)
				return list
			else:
				end=mid_point
		else:
			if (end-start)<2:
				list.insert(end, value)
				return list
			else:
				start=mid_point

for i in range(K):
   Alist[0]=Alist[0]/2
   value=Alist.pop(0)
   Alist=insert_list(Alist,value)
sum=0
#print(Alist)
for i in Alist:
   sum+=math.floor(i) 
print(int(sum))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
val = list(map(int,input().split()))
my_index = val.index
for _in range(m):
  val[my_index(max(val))] = max(val)//2
print(sum(val))

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))

Alist = [int(i) for i in input().split(' ')]
import math

#print(Alist)
my_list = [9,8,7,4,7,1,3]

Alist=sorted(Alist, reverse=True)
#print(sorted(Alist, reverse=True))


for i in range(K):
   Alist[0]=Alist[0]/2
   if N>1: 
      if Alist[0]<Alist[1]:
         temp=Alist[0]
         Alist[0]=Alist[1]
         Alist[1]=temp
         continue          
      if Alist[0]<Alist[i]:
         temp=Alist[0]
         Alist[0]=Alist[i]
         Alist[i]=temp
         continue
      if i>2:
         if Alist[0]<Alist[i-1]:
            temp=Alist[0]
            Alist[0]=Alist[i-1]
            Alist[i-1]=temp
            continue
   Alist=sorted(Alist, reverse=True)
sum=0
#print(Alist)
for i in Alist:
   sum+=math.floor(i) 
print(int(sum))

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))

Alist = [int(i) for i in input().split(' ')]
import math

#print(Alist)
my_list = [9,8,7,4,7,1,3]

Alist=sorted(Alist, reverse=True)
#print(sorted(Alist, reverse=True))


for i in range(K):
   Alist[0]=Alist[0]/2
   if N>1: 
      if Alist[0]<Alist[1]:
         temp=Alist[0]
         Alist[0]=Alist[1]
         Alist[1]=temp
      if Alist[0]<Alist[i]:
         temp=Alist[0]
         Alist[0]=Alist[i]
         Alist[i]=temp
      if i>2:
         if Alist[0]<Alist[i-1]:
            temp=Alist[0]
            Alist[0]=Alist[i-1]
            Alist[i-1]=temp
sum=0
#print(Alist)
for i in Alist:
   sum+=math.floor(i) 
print(int(sum))

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))

Alist = [int(i) for i in input().split(' ')]
import math

#print(Alist)
my_list = [9,8,7,4,7,1,3]

Alist=sorted(Alist, reverse=True)
#print(sorted(Alist, reverse=True))


for i in range(K):
   Alist[0]=Alist[0]/2
   if N>1: 
      if Alist[0]<Alist[1]:
         temp=Alist[0]
         Alist[0]=Alist[1]
         Alist[1]=temp
      if Alist[0]<Alist[i]:
         temp=Alist[0]
         Alist[0]=Alist[i]
         Alist[i]=temp
sum=0
#print(Alist)
for i in Alist:
   sum+=math.floor(i) 
print(int(sum))

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
Alist = [int(i) for i in input().split(' ')]
import math

my_list = [9,8,7,4,7,1,3]

Alist=sorted(Alist, reverse=True)

for i in range(K):
   Alist[0]=Alist[0]/2
   if N>1: 
      if Alist[0]<Alist[1]:
         temp=Alist[0]
         Alist[0]=Alist[1]
         Alist[1]=temp
      if Alist[0]<Alist[i]:
         temp=Alist[0]
         Alist[0]=Alist[i]
         Alist[i]=temp
sum=0

for i in Alist:
   sum+=math.floor(i) 
print(sum)

Submission status: Runtime Error

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

A.sort(reverse=True)
#print(A)

for m in range(M-1):
    A[0] //= 2
    for n in range(N):
        if A[n] < A[n+1]:
            #print("{} <-> {}".format(A[n], A[n+1]))
            A[n], A[n+1] = A[n+1], A[n]
        else:
            break

A[0] //= 2
#print(A)
print(sum(A))

Submission status: Runtime Error

Solution code:
#AtCoder

import sys
import math
import itertools
input = sys.stdin.readline

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

A.sort(reverse=True)

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

for _ in range(M):
	A[0] = A[0] // 2
	if A[0] < A[1]:
		left = 1
		right = N-1
		while left != right-1:
			if A[0] < A[(left+right)//2]:
				left = (left+right)//2
			else:
				right = (left+right)//2
			print(left, right)
		
		i = right
		head = A[1:i]
		head.append(A[0])
		tail = A[i:]
		A = head + tail
		print(head,tail)


sum = 0
for i in range(len(A)):
	sum += A[i]

print(sum)



"""

"""

Submission status: Runtime Error

Solution code:
N,M = [int(i) for i in input().split(' ')]
itemList = [int(i) for i in input().split(' ')]
heap = []

for i in itemList:
    heappush(heap, -i)

for _ in range(M):
    heappush(heap, math.ceil(heappop(heap)/2))
print(-sum(heap))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lis=list(map(int,input().split()))
lis.sort()
t=0
a=0
c=0
for i in range (0,n):
  t=t+lis[i]
for i in range (0,m):
  k=lis[n-1]
  b=k//2
  a=a+k-b
  lis[n-1]=b
  del lis[n-1]
  while lis[c]<b and c<=n-1:
    c+=1
  lis.insert(c,b)
print(t-a)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lis=list(map(int,input().split()))
lis.sort()
t=0
a=0
c=1
for i in range (0,n):
  t=t+lis[i]
for i in range (0,m):
  k=lis[n-1]
  b=k//2
  a=a+k-b
  lis[n-1]=b
  del lis[n-1]
  while lis[c-1]<b and c-1<=n-1:
    c+=1
  lis.insert(c,b)
  print(lis)
print(t-a)

Submission status: Runtime Error

Solution code:
class Heap:

    # 初期化
    def __init__(self):
        self.array = []

    def num(self):
        return len(self.array)
        
    # valを追加する
    def put(self, val):
        pos = len(self.array)
        # valを末尾に追加する
        self.array.append(val)
        # valを適当な位置まで上にあげる
        self.pop_up(pos)
        
    # 最大の要素を取り出す
    def get(self):
        assert len(self.array) > 0

        val = self.array[0]
        
        # 末尾の要素を0に移動してから下に下げる
        t_val = self.array[-1]
        self.array[0] = t_val
        del self.array[-1]
        self.push_down(0)
        return val

    # posの位置の要素を適当な位置まで上げる
    def pop_up(self, pos):
        while pos > 0:
            p_pos = (pos - 1) // 2
            val = self.array[pos]
            p_val = self.array[p_pos]
        
            if val > p_val:
                self.array[pos] = p_val
                self.array[p_pos] = val
                pos = p_pos
            else:
                break
            
    def push_down(self, pos):
        while True:
            l_pos = 2 * pos + 1
            r_pos = 2 * pos + 2
            n = len(self.array)
            
            if n <= l_pos:
                # 子がいない場合
                break
            
            elif n == r_pos:
                # 子が一人の場合
                val = self.array[pos]
                l_val = self.array[l_pos]
                
                if val < l_val:
                    self.array[pos] = l_val
                    self.array[l_pos] = val
                    
                break #
            
            else:
                # 子が二人いるとき
                val = self.array[pos]
                l_val = self.array[l_pos]
                r_val = self.array[r_pos]
                
                if l_val > r_val:
                    if val < l_val:
                        self.array[pos] = l_val
                        self.array[l_pos] = val
                        pos = l_pos
                    else:
                        break
                else:
                    if val < r_val:
                        self.array[pos] = r_val
                        self.array[r_pos] = val
                        pos = r_pos
                    else:
                        break

                        
h = Heap()
sn,sm = input().split(" ")
n = int(sn)
m = int(sm)
sa_list = input().split(" ")
l = len(sa)

for sa in sa_list:
  a = int(sa)  
  h.put(a)
 
for i in range(m):  
    max_a = h.get()
    h.put(max_a // 2)

    

print(sum(h.array))