You have the golden opportunity to stay at the world's best hotel, which is renowned for its food. There are exactly N buffets in this hotel and each buffet contains Bi amount of food. Every time you enter a buffet, you need to pay with 1 buffet voucher. You have been given exactly k buffet vouchers to spend. Once you enter the buffet, you eat all the food present in that buffet, and you leave the buffet once you finish eating. Once you have left, the hotel staff refill the buffet with half of the previous amount of food present (i.e if there were 4 units of food present earlier, they refill it with 2 units, if there were 5 units of food present earlier, they refill it with 2 units, i.e floor(x/2) ). You can enter a buffet multiple times. Your task is to find out the maximum amount of food you can eat.Input FormatFirst line contains an integer T. T test cases follow. First line of each test case contains two space-separated integers N and K. Second line of each test case contains N space-separated integers, the amount of food in each buffetConstraints1 ≤ T ≤ 101 ≤ N ≤ 1050 ≤ K ≤ 1050 ≤ Bi ≤ 1010Output FormatPrint the answer to each test case in a new line.Sample Input 015 32 1 7 4 2Sample Output 014Explanation 0You give your 1st coupon voucher and you eat 7 amounts of food. The hotel staff refills the item with 3 amounts of food, You spend your 2nd voucher and eat 4 amounts of food. The hotel staff refills it with 2 amount of food. You spend your 3rd voucher and eat 3 amounts of food. The hotel staff refills it with 1 amount of food. Hence amount you ate: 7 + 4 + 3 = 14

import heapq

def max_food(T, test_cases):
    for _ in range(T):
        N, K, B = test_cases[_]
        B = [-1*i for i in B]  # Convert to max heap
        heapq.heapify(B)
        total = 0
        for _ in range(K):
            if B:
                food = heapq.heappop(B)
                total -= food
                if food // 2 != 0:
                    heapq.heappush(B, food // 2)
        print(total)

T = 1
test_cases = [
    (5, 3, [2, 1, 7, 4, 2])
]
max_food(T, test_cases)