public static string highestValuePalindrome(string s, int n, int k)
{
    if (k >= n)
    {
        var chars = Enumerable.Repeat('9', n).ToArray();
        return new string(chars);
    }

    if (n == 1 && k > 0) return "9";
    var InvRequiredIndexes = MinChangesMakingPalindrome(s);
    var setInvRequiredIndexes = InvRequiredIndexes.ToHashSet();
    var minChangesRequired = InvRequiredIndexes.Count;
    if (minChangesRequired > k) return "-1";
    var theChars = s.ToCharArray();
    if (minChangesRequired == k)
    {
        foreach (var i in InvRequiredIndexes)
        {
            if (theChars[i] > theChars[n - i -1]) theChars[n - i -1] = theChars[i];
            else theChars[i] = theChars[n - i -1];
        }
        return new string(theChars);
    }
    // k is > minChangesRequired
    var additionalChangesAvailable = k - minChangesRequired;
    while(additionalChangesAvailable > 0)
    {
        for (var i = 0; i < n / 2 && additionalChangesAvailable > 0; i++)
        {
            if (setInvRequiredIndexes.Contains(i)) // just 1 additional change needed
            {
                if(theChars[i] != '9' && theChars[n - i - 1] != '9') additionalChangesAvailable--;
                theChars[i] = theChars[n - i - 1] = '9';
                setInvRequiredIndexes.Remove(i);                        
            }
            else if(theChars[i] != '9' && additionalChangesAvailable >= 2)
            {
                theChars[i] = theChars[n - i - 1] = '9';
                additionalChangesAvailable -= 2;
            }
        }
        break;
    }

    // Done with the additional changes. Now cary out the mandatory changes if any left
    var lstInvRequiredIndexes = setInvRequiredIndexes.ToList();
    for (var i = 0; i < lstInvRequiredIndexes.Count; i++)
    {
        var ind = lstInvRequiredIndexes[i];
        if(additionalChangesAvailable > 0)
        {
            theChars[n - ind - 1] = theChars[ind] = '9';
            additionalChangesAvailable--;
        }
        else if (theChars[ind] < theChars[n - ind - 1]) theChars[ind] = theChars[n - ind - 1];
        else theChars[n - ind - 1] = theChars[ind];
    }
    if (n % 2 != 0 && additionalChangesAvailable > 0) theChars[n / 2] = '9';
    return new string(theChars);
}

public static List<int> MinChangesMakingPalindrome(string s)
{
    var len = s.Length;
    var halfLen = len / 2;
    var invIndexes = new List<int> { };
    for(var i = 0; i < halfLen; i++)
    {
        if (s[i] != s[len - i -1]) invIndexes.Add(i);
    }
    return invIndexes;
}