AtCoder Beginner Contest 141 [ D - Powerful Discount Tickets ] https://atcoder.jp/contests/abc141/tasks/abc141_d

abc141_d.py

'''
[問題]
https://atcoder.jp/contests/abc141/tasks/abc141_d

[解説]
https://youtu.be/fHZhDUzhzN0?t=1341
 割引券を何枚割り当てるか？
 という考えではなく、１枚づつ最大の値段の商品に使っていけば、おのずと答えは出る。
'''

import sys
import heapq

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

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

# 各要素を-1倍
A = list(map(lambda x: x*(-1), A))
# リストを優先度付きキューへ
heapq.heapify(A)

for _ in range(M):
    # -1になってるので最小値だが(優先度付きキューは最小値しか取れない)、最大値
    max_a = heapq.heappop(A)
    # 負のまま割り算すると切り捨て計算の結果は異なる。13//2 = 6, -13//2 = -7
    n = max_a*-1 // 2
    # 優先度付きキューに追加
    heapq.heappush(A, -1*n)

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