<p>You are given an integer array <code>gifts</code> denoting the number of gifts in various piles. Every second, you do the following:</p>

<ul>
	<li>Choose the pile with the maximum number of gifts.</li>
	<li>If there is more than one pile with the maximum number of gifts, choose any.</li>
	<li>Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.</li>
</ul>

<p>Return <em>the number of gifts remaining after </em><code>k</code><em> seconds.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> gifts = [25,64,9,4,100], k = 4
<strong>Output:</strong> 29
<strong>Explanation:</strong> 
The gifts are taken in the following way:
- In the first second, the last pile is chosen and 10 gifts are left behind.
- Then the second pile is chosen and 8 gifts are left behind.
- After that the first pile is chosen and 5 gifts are left behind.
- Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> gifts = [1,1,1,1], k = 4
<strong>Output:</strong> 4
<strong>Explanation:</strong> 
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. 
That is, you can&#39;t take any pile with you. 
So, the total gifts remaining are 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= gifts.length &lt;= 10<sup>3</sup></code></li>
	<li><code>1 &lt;= gifts[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>3</sup></code></li>
</ul>

class Solution:
    def pickGifts(self, gifts, k):
        # Max-Heap functions
        def heapify(arr):
            n = len(arr)
            for i in range(n // 2 - 1, -1, -1):
                sift_down(arr, i, n)
        
        def heappush(arr, val):
            arr.append(val)
            sift_up(arr, len(arr) - 1)
        
        def heappop(arr):
            n = len(arr)
            if n == 0:
                return None
            if n == 1:
                return arr.pop()
            top = arr[0]
            arr[0] = arr.pop()
            sift_down(arr, 0, len(arr))
            return top
        
        def sift_up(arr, idx):
            while idx > 0:
                parent = (idx - 1) // 2
                if arr[idx] > arr[parent]:
                    arr[idx], arr[parent] = arr[parent], arr[idx]
                    idx = parent
                else:
                    break
        
        def sift_down(arr, idx, n):
            while True:
                largest = idx
                left = 2 * idx + 1
                right = 2 * idx + 2
                if left < n and arr[left] > arr[largest]:
                    largest = left
                if right < n and arr[right] > arr[largest]:
                    largest = right
                if largest != idx:
                    arr[idx], arr[largest] = arr[largest], arr[idx]
                    idx = largest
                else:
                    break
        
        # Initialize max-heap
        heap = gifts[:]
        heapify(heap)
        
        for _ in range(k):
            if not heap:
                break
            # Pop the pile with the maximum number of gifts
            max_gifts = heappop(heap)
            # Calculate the new number of gifts
            remaining_gifts = int(max_gifts ** 0.5)
            # If remaining gifts are more than zero, push back into heap
            if remaining_gifts > 0:
                heappush(heap, remaining_gifts)
        
        # Sum up the remaining gifts
        total_gifts = sum(heap)
        return total_gifts

# Example usage:

# Example 1
gifts1 = [25, 64, 9, 4, 100]
k1 = 4
solution = Solution()
print(solution.pickGifts(gifts1, k1))  # Output: 29

# Example 2
gifts2 = [1, 1, 1, 1]
k2 = 4
print(solution.pickGifts(gifts2, k2))  # Output: 4

61