public static string HighestValuePalindrome(string s, int k) {
        char[] chars = s.ToCharArray();
        
        // calculate count of unbalanced pairs in the string
        int m = 0;
        int i1 = 0;
        int j1 = s.Length - 1;

        while(i1 < j1) {
            if(s[i1] != s[j1])
                m++;
            i1++;
            j1--;
        }

        // it is not enough 'k' in advance
        if(k < m)
            return "-1";

        int i2 = 0;
        int j2 = s.Length - 1;

        // we prefer both '9' if possible
        while(i2 < j2) {
            if(CanSetBoth9Digits()) {
                chars[i2] = chars[j2] = '9';
                k -= 2;
                if(s[i2] != s[j2])
                    m -= 1;
            }
            else if(s[i2] > s[j2]) {
                chars[j2] = chars[i2];
                k--;
                m--;
            }
            else if(s[i2] < s[j2]) {
                chars[i2] = chars[j2];
                k--;
                m--;
            }

            i2++;
            j2--;
        }
        
        if(i2 == j2 && k > 0)
            chars[i2] = '9';
        
        return new string(chars);


        bool CanSetBoth9Digits() {
            if(s[i2] == '9' || s[j2] == '9')
                return false;
            bool digitsEqual = s[i2] == s[j2];
            return (!digitsEqual && k > m) || (digitsEqual && k > m + 1);
        }
    }