#include <bits/stdc++.h>
using namespace std;
const int MAX = 10010;
int N, K;
int d[10];
char s[MAX], tmp[MAX], sol[MAX];
vector<int> pos[10];
int main() {
  scanf("%d %d\n", &N, &K);
  gets(s);
  for (int i = 0; s[i]; i++) {
    d[s[i] - '0']++;
    pos[s[i] - '0'].push_back(i);
  }
  int bst = 1 << 30;
  for (int i = 0; i < 10; i++) {
    int k = d[i], lo = i - 1, hi = i + 1, cur = 0;
    memcpy(tmp, s, sizeof(s));
    while (k < K) {
      if (hi < 10)
        for (vector<int>::iterator it = pos[hi].begin();
             it != pos[hi].end() && k < K; it++) {
          tmp[*it] = i + '0';
          cur += hi - i;
          k++;
        }
      if (lo >= 0)
        for (vector<int>::reverse_iterator it = pos[lo].rbegin();
             it != pos[lo].rend() && k < K; it++) {
          tmp[*it] = i + '0';
          cur += i - lo;
          k++;
        }
      ++hi;
      --lo;
    }
    if (bst > cur || (bst == cur && strcmp(tmp, sol) < 0)) {
      bst = cur;
      memcpy(sol, tmp, sizeof(tmp));
    }
  }
  printf("%d\n", bst);
  puts(sol);
  return 0;
}
