class Solution {
    public long rearrange(int x) {
      int[]freqarray =new int[10];
      int result=0;
     
      while(x>0){
        int digit=x%10;
        freqarray[digit]++;
        x=x/10;
      }        

      for(int digit=9;digit>=0;digit--){
        while(freqarray[digit] > 0){
            result=result*10+digit;
            freqarray[digit]--;
        }
      }

      return result;
    }
    public long maximizeSum(int[] nums, int k) {
        int n=nums.length;
        long[]gain =new long[n];
        
        long sum_orig=0;
        for(int i=0;i<n;i++){
           sum_orig+=nums[i];
        }
        for(int i=0;i<n;i++){
            gain[i]=rearrange(nums[i])-nums[i];
        }
        Arrays.sort(gain);
        
        long res=0;
        int c=0;
        for(int i=n-1;i>=0;i--){
            c++;
            if(c>k){
                break;
            }
            res+=gain[i];
        }
        res+=sum_orig;

        return res;
    }
}