Question
Bargain Blitz
Zara enters a store with M item types, each with a price qi for the ith item. She holds B discount vouchers. Using Y vouchers on the ith item reduces its price to floor(qi / 2y). Determine the minimum total cost to purchase one of each item type.
Input
The first line of the input contains two space-separated integers N and A.
The second line of the input contains N space-separated integers.
Constraints
1 ≤ N ≤ 105
1 ≤ qi ≤ 109
1 ≤ A ≤ 105
The second line of the input contains N space-separated integers.
Constraints
1 ≤ N ≤ 105
1 ≤ qi ≤ 109
1 ≤ A ≤ 105
Output
Print the minimum total cost to purchase one of each item type.
Example
Sample Input
5 4
10 4 7 8 2
Sample Output
15
Explanation
You use 2 coupons on item 1, 1 coupon on item 3 and the last coupon on item 4.
This will make the price array of items as [2, 4, 3, 4, 2].
Total cost = 2 + 4 + 3 + 4 + 2 = 15
5 4
10 4 7 8 2
Sample Output
15
Explanation
You use 2 coupons on item 1, 1 coupon on item 3 and the last coupon on item 4.
This will make the price array of items as [2, 4, 3, 4, 2].
Total cost = 2 + 4 + 3 + 4 + 2 = 15