Paste: 2195

typedef long long ll; 
class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        ll res = 0; 
        sort(nums.begin(), nums.end()); 
        int p = 0, i = 1, j = 1; 
        while (k && p < nums.size()) {
            while (j < nums[p] && k) {
                j++; k--; 
            }
            res += (ll)((i + j - 1) * (j - i)) / 2; 
            p++; 
            j++; i = j; 
        }
        return (ll)(2 * (nums.back() + 1) + k - 1) * k / 2 + res; 
    }
};