public static string highestValuePalindrome(string s, int n, int k)
    {
        int left = 0, right = s.Length - 1;
        int remain = k;
        List<char> newS = new List<char>(s);
        List<bool> changedMark = Enumerable.Repeat(false, n).ToList();
        while (left < right){
            if (remain <= 0 && newS[left] != newS[right]) return "-1"; 
            if (newS[left] != newS[right]){
                remain--;
                if (newS[left] > newS[right]) newS[right] = newS[left];
                if (newS[right] > newS[left]) newS[left] = newS[right];
                   changedMark[left] = true; 
            }
            left++;
            right--;
        }
        left = 0; right = s.Length - 1;
        while (remain > 0 && left < right){    
            if (newS[left] != '9'){             
                if (changedMark[left])
                { 
                    newS[left] = newS[right] = '9';
                    changedMark[left] = false; 
                    remain --;
                }
                else if (remain >= 2){
                    newS[left] = newS[right] = '9';
                    changedMark[left] = false; 
                    remain -=2;
                }
            }
            left++;
            right--;      
        }     
        if (remain >= 1 && n % 2 == 1) newS[n/2] = '9';
        string result = new string(newS.ToArray());
        return result;
    }
}