def highestValuePalindrome(s, n, k):
    sArr = list(s)
    half = (n >> 1) + 1
    count = k
    
    # check non-palindrome
    idxL, idxR = 0, n - 1
    while idxL <= idxR:
        if sArr[idxL] != sArr[idxR]:
            # use the max value of them
            sArr[idxL] = sArr[idxR] = max(sArr[idxL], sArr[idxR])
            count -= 1
        # if there are more than k invalid digits, return -1 
        if count < 0:
            return '-1'
        idxL, idxR = idxL + 1, idxR - 1
        
    # repalce 9
    idxL, idxR = 0, n - 1
    while idxL <= idxR:
        if idxL == idxR:
            # if it is the middle one(odd length), try to set the digit to 9
            if count > 0:
                sArr[idxL] = '9'
        else:
            deduct = 0
            if sArr[idxL] < '9':
                # set the pair of digits to 9 if it is necessary
                if sArr[idxL] != s[idxL] or sArr[idxR] != s[idxR]:
                    # if this pair of digits are invalid, reduce by 1, 
                    # because the counter has already decrased by 1 before
                    deduct = 1
                else:
                    # otherwise, decrease the counter by 2
                    deduct = 2
                    
                # if the counter is still greater or equals to 0, execute it  
                if (count - deduct) >= 0:
                    sArr[idxL] = sArr[idxR] = '9'
                    count -= deduct
                    
        idxL, idxR = idxL + 1, idxR - 1
    
    return ''.join(sArr)