void largest_pal(string& s, int n, int& k, vector<bool>& changed){
    int l=0,h=n-1;
    
    while(l<=h && k>0){
        if(l == h){ //middle
            if(k > 0 && s[l] != '9'){
                s[l] = '9';
                k--;
            }
        }
        else {
        if (s[l] != '9') {
            if (changed[l] || changed[h]) {
                // Only 1 change needed to upgrade both to '9'
                if (k >= 1) {
                    s[l] = s[h] = '9';
                    k--;
                }
            } else if (k >= 2) {
                // 2 changes needed to upgrade both to '9'
                s[l] = s[h] = '9';
                k -= 2;
            }
         }
       }
       l++; h--;
    }
}
string highestValuePalindrome(string s, int n, int k) {
    vector<bool>changed(n,false);
    // int val = check_palindrome(s,n,k,changed);
    int l=0,h=n-1;
    //First pass: Make the string a palindrome with minimal changes, record changed positions
    while(l <= h){
        if(s[l] != s[h]){
            
            if(k == 0)
                return "-1";
            
            if(s[l] > s[h])
                s[h] = s[l];
            else 
                s[l] = s[h];
            
            k--;
            changed[l] = changed[h] = true;       
        }
    l++; h--;
    }
    
    //Second pass: Maximize the palindrome by upgrading pairs to '9'
   
    // if(n%2 == 1 && k==1){
    //     s[n/2] = '9';
    //     return s;
    // }
    
        largest_pal(s,n,k,changed);
    
    
    
    return s;
}