public static String highestValuePalindrome(String s, int n, int k) {
                char c [] = s.toCharArray();  
                int N=n/2; int j=-1;
                boolean [] B = new boolean [N];
                for(int i=0;i<N; i++){
                        B[i]=c[i]==c[n-i-1];
                        if(!B[i]&&--k<0)return "-1";
                        c[i]=(char)(Math.max(c[i],c[n-i-1]));
                        c[n-1-i]=c[i];
                }
                while(k>0&&++j<N){
                        if(c[j]!='9'&&((B[j]&&k>1)||(k>0&&!B[j]))){
                                c[j]='9'; c[n-j-1]='9';
                                k=k+(B[j]?-2:-1);
                        }
                }
                if(n%2==1&&k>0)c[N]='9';
                return new String(c);
        }
}