def highestValuePalindrome(s, n, k): # convert to list so we can modify characters s = list(s) changed = [False] * n # track positions changed in phase 1 i, j = 0, n - 1 used = 0

# Phase 1: make the string a palindrome with minimal changes
while i < j:
    if s[i] != s[j]:
        # replace the smaller digit with the larger one
        if s[i] > s[j]:
            s[j] = s[i]
        else:
            s[i] = s[j]
        changed[i] = changed[j] = True
        used += 1
    i += 1
    j -= 1

# if we already used more changes than allowed, impossible
if used > k:
    return '-1'

# Phase 2: maximize the palindrome using remaining changes
remaining = k - used
i, j = 0, n - 1
while i <= j:
    if i == j:
        # middle digit in odd-length string: can make it '9' with one remaining change
        if remaining > 0:
            s[i] = '9'
        # else leave as is
    else:
        if s[i] != '9':
            # if either side was changed in phase 1, upgrading both to '9' costs 1 extra change
            if changed[i] or changed[j]:
                if remaining >= 1:
                    s[i] = s[j] = '9'
                    remaining -= 1
            # if neither side was changed before, upgrading both to '9' costs 2 changes
            elif remaining >= 2:
                s[i] = s[j] = '9'
                remaining -= 2
    i += 1
    j -= 1

return ''.join(s)