#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
int main() {
  const int ORD[10][9] = {
      {1, 2, 3, 4, 5, 6, 7, 8, 9}, {2, 0, 3, 4, 5, 6, 7, 8, 9},
      {3, 1, 4, 0, 5, 6, 7, 8, 9}, {4, 2, 5, 1, 6, 0, 7, 8, 9},
      {5, 3, 6, 2, 7, 1, 8, 0, 9}, {6, 4, 7, 3, 8, 2, 9, 1, 0},
      {7, 5, 8, 4, 9, 3, 2, 1, 0}, {8, 6, 9, 5, 4, 3, 2, 1, 0},
      {9, 7, 6, 5, 4, 3, 2, 1, 0}, {8, 7, 6, 5, 4, 3, 2, 1, 0},
  };
  int n, k;
  char s[10001];
  scanf("%d%d%s", &n, &k, s);
  int freq[10] = {};
  for (int i = 0; i < (n); i++) freq[s[i] - '0']++;
  int ans = INF;
  char s_ans[10001];
  for (int to = 0; to < (10); to++) {
    int cost = 0, f = freq[to], use[10] = {};
    for (int i = 0; i < (9); i++) {
      int from = ORD[to][i];
      if (f >= k) break;
      if (k - f < freq[from]) {
        cost += abs(to - from) * (k - f);
        use[from] += k - f;
        f = k;
      } else {
        cost += abs(to - from) * freq[from];
        use[from] += freq[from];
        f += freq[from];
      }
    }
    static char s_tmp[10001];
    strcpy(s_tmp, s);
    for (int i = 0; i < (9); i++) {
      int from = ORD[to][i];
      if (from < to) {
        for (int i = n - 1; i >= 0; i--) {
          if (use[from] > 0 && s[i] == from + '0')
            s_tmp[i] = to + '0', use[from]--;
        }
      } else {
        for (int i = 0; i < (n); i++) {
          if (use[from] > 0 && s[i] == from + '0')
            s_tmp[i] = to + '0', use[from]--;
        }
      }
    }
    if (cost < ans || cost == ans && strcmp(s_tmp, s_ans) < 0) {
      ans = cost;
      strcpy(s_ans, s_tmp);
    }
  }
  printf("%d\n%s\n", ans, s_ans);
  return 0;
}
