def highestValuePalindrome(s, n, k):
    s = list(s)
    s = [int(ele) for ele in s]
    
    modified_idxs = set()
    
    # create any palindrom
    for left_idx in range(0, n // 2):
        right_idx = n - 1 - left_idx
        
        if s[left_idx] != s[right_idx]:
            if k >= 1:
                # change one to greater val
                max_val = max(s[left_idx], s[right_idx])
                s[left_idx] = max_val
                s[right_idx] = max_val
                k -= 1
                modified_idxs.add(left_idx)
            else:
                # not palindrome and can't do any more changes so return -1
                return "-1"
                
    # here we know palindrome can be created, now let's max it
    for left_idx in range(0, n // 2):
        if k < 1:
            break
            
        right_idx = n - 1 - left_idx
        
        if s[left_idx] == 9 and s[right_idx] == 9:
            # can't do any better
            continue

        if left_idx in modified_idxs and k >= 1:
            # already modified, so we need just one change to change two numbers
            s[left_idx] = 9
            s[right_idx] = 9
            k -= 1
        elif k >= 2:
            # not modified yet, we need to changes to change to 9s
            s[left_idx] = 9
            s[right_idx] = 9
            k -= 2
        
    # handle middle
    if n % 2 == 1 and k >= 1:
        middle_idx = n // 2
        s[middle_idx] = 9
            
    return "".join([str(ele) for ele in s])