<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. Append <code>k</code> <strong>unique positive</strong> integers that do <strong>not</strong> appear in <code>nums</code> to <code>nums</code> such that the resulting total sum is <strong>minimum</strong>.</p>

<p>Return<em> the sum of the</em> <code>k</code> <em>integers appended to</em> <code>nums</code>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,4,25,10,25], k = 2
<strong>Output:</strong> 5
<strong>Explanation:</strong> The two unique positive integers that do not appear in nums which we append are 2 and 3.
The resulting sum of nums is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum.
The sum of the two integers appended is 2 + 3 = 5, so we return 5.</pre>

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

<pre>
<strong>Input:</strong> nums = [5,6], k = 6
<strong>Output:</strong> 25
<strong>Explanation:</strong> The six unique positive integers that do not appear in nums which we append are 1, 2, 3, 4, 7, and 8.
The resulting sum of nums is 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36, which is the minimum. 
The sum of the six integers appended is 1 + 2 + 3 + 4 + 7 + 8 = 25, so we return 25.
</pre>

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

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

def cumulative_sum(n):
    return (n * (n+1))//2 

class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:

        nums.sort()
        nums_added = 0
        total_sum_add = 0

        if nums[0] > 1:
            num_diff = nums[0] - 1
            if num_diff <= k:
                nums_added += num_diff
                total_sum_add += cumulative_sum(nums[0]-1) 
            else:
                total_sum_add += cumulative_sum(k)
                return total_sum_add

        for i in range(1, len(nums)):
            nums_to_add = k - nums_added
            num_diff = nums[i] - nums[i-1] - 1

            if num_diff > 0:
                if num_diff <= nums_to_add:
                    nums_added += num_diff
                    total_sum_add += cumulative_sum(nums[i]-1) - cumulative_sum(nums[i-1]) 

                else:
                    total_sum_add += cumulative_sum(nums[i-1] + nums_to_add) - cumulative_sum(nums[i-1])
                    return total_sum_add

        nums_to_add = k - nums_added
        total_sum_add += cumulative_sum(nums[-1] + nums_to_add) - cumulative_sum(nums[-1])
        return total_sum_add
            


# class Solution:
#     def minimalKSum(self, nums: List[int], k: int) -> int:
#         nums.sort()
#         nums_added = 0
#         total_sum_add = 0
        
#         # Add missing numbers from 1 to the first number in the sorted list
#         if nums[0] > 1:
#             num_diff = nums[0] - 1
#             if num_diff <= k:
#                 nums_added += num_diff
#                 total_sum_add += cumulative_sum(nums[0] - 1)
#             else:
#                 total_sum_add += cumulative_sum(k)
#                 return total_sum_add

#         # Loop through the sorted numbers to find gaps
#         for i in range(1, len(nums)):
#             nums_to_add = k - nums_added
#             num_diff = nums[i] - nums[i-1] - 1

#             if num_diff > 0:
#                 if num_diff <= nums_to_add:
#                     nums_added += num_diff
#                     total_sum_add += cumulative_sum(nums[i] - 1) - cumulative_sum(nums[i-1])
#                 else:
#                     total_sum_add += cumulative_sum(nums[i-1] + nums_to_add) - cumulative_sum(nums[i-1])
#                     return total_sum_add

#         # Add remaining numbers if needed
#         nums_to_add = k - nums_added
#         total_sum_add += cumulative_sum(nums[-1] + nums_to_add) - cumulative_sum(nums[-1])
#         return total_sum_add

519