Minimum Sum After K Halvings

You are given a list of integers nums and an integer k.

Consider an operation where you pick one element x of nums and replace it with ceil(x / 2), the smallest integer that is greater than or equal to x / 2. The same element may be picked any number of times.

Given that you must perform this operation exactly k times, return the minimum possible sum of nums afterwards.

Note that ceil(1 / 2) is 1, so an operation on an element equal to 1 leaves it unchanged.

Examples

Example 1

Input: nums = [10,20,7], k = 3
Output: 17
Explanation: Replace 20 with ceil(20 / 2) = 10, giving [10,10,7]. Replace one 10 with 5,
giving [5,10,7]. Replace the other 10 with 5, giving [5,5,7]. The sum is 17. Spending two
operations on the same 10 instead (10 becomes 5, then 3) leaves the other 10 untouched and
gives [3,10,7] with sum 20, so 17 is the minimum.

Example 2

Input: nums = [5], k = 2
Output: 2
Explanation: 5 becomes ceil(5 / 2) = 3, then 3 becomes ceil(3 / 2) = 2.

Example 3

Input: nums = [3,1,1], k = 4
Output: 3
Explanation: Two operations turn 3 into 2 and then into 1. The remaining two operations
must still be performed, but every element is now 1, so they change nothing. The sum is 3.