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.

The problem is asking to find the maximum amount of food you can eat given a certain number of buffet vouchers and a list of buffets with varying amounts of food. Here's a step-by-step guide on how to solve this problem:

1. First, we need to understand the problem and the constraints. We have a number of buffets, each with a certain amount of food. We also have a certain number of buffet vouchers. Each time we enter a buffet, we consume all the food there and the buffet is then refilled with half the previous amount of food. We can enter a buffet multiple times.

2. We need to find the maximum amount of food we can eat. To do this, we should always choose the buffet with the most food. This is because we want to maximize the amount of food we eat with each voucher.

3. We can use a priority queue to keep track of the buffets. The priority queue will automatically sort the buffets in descending order of the amount of food. We initialize the priority queue with the initial amounts of food in the buffets.

4. We then start using our vouchers. Each time we use a voucher, we choose the buffet at the top of the priority queue (which is the buffet with the most food). We eat all the food in that buffet and then calculate the new amount of food in the buffet (which is half the previous amount, rounded down). We then update the priority queue with this new amount.

5. We repeat this process until we have used all our vouchers. The total amount of food we have eaten is the sum of the food we ate each time we used a voucher.

6. Finally, we print the total amount of food we have eaten. This is the solution to the problem.

This algorithm will ensure that we always eat the maximum amount of food possible with our vouchers. The time complexity of this algorithm is O(K log N), where K is the number of vouchers and N is the number of buffets. This is because each operation on the priority queue takes log N time and we perform K such operations.