Ajay has N lockers with money in it. The i'th of these lockers contains R_i rupees. He opens a locker, takes all the money from it and locks it. But as soon as he locks the locker, the money in the locker increases magically! Say the locker that used to contain X rupees(before taking), now contains [X/2] rupees! ,where [x] is floor of x (floor). Ajay can now have a lot more money! But all the locker will disappear in M minutes. In a single minute, Ajay can take all the money from a single locker, regardless of the total money in it.
Find the maximum money that Ajay can take.

Input:
First line contains an integer T. T test cases follow.
First line of each test case contains two space-separated integers N and M.
Second line of each test case contains N space-separated integers, total rupees in the lockers

Output:
Print the answer to each test case in a new line.

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10⁵
0 ≤ M ≤ 10⁵
0 ≤ R_i ≤ 10¹⁰