Minimize sum with halving operations

You are given an array of non-negative integers nums and an integer k. In one operation, choose any index i and replace nums[i] with ceil(nums[i] / 2). You may perform at most k operations. Return the minimum possible sum of the array after the operations. Describe an efficient algorithm, prove why it works, analyze time and space complexity, and discuss edge cases such as zeros and very large k.