1967A - Permutation Counting - CodeForces Solution

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    tt = int(data[idx])
    idx += 1
    results = []
    
    for _ in range(tt):
        n = int(data[idx])
        k = int(data[idx + 1])
        idx += 2
        v = list(map(int, data[idx:idx + n]))
        idx += n
        
        v.sort()
        small = v[0]
        ind = -1
        
        for i in range(1, n):
            x = (v[i] - v[i - 1]) * i
            if x > k:
                break
            else:
                k -= x
                small = v[i]
                ind = i
        
        if ind == -1:
            results.append(str((small + k) * n))
            continue
        
        num = ind + 1
        small += k // num
        num -= k % num
        result = (n - num) * small + small + (num - 1) * (small - 1)
        results.append(str(result))
    
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    main()