#include <bits/stdc++.h>
using namespace std;
char st[10005], ss[10005], Minstr[10005];
int cnt[11];
int main() {
  int n, k, Min, t, tmp, ans;
  while (scanf("%d %d", &n, &k) != EOF) {
    scanf("%s", st);
    Min = 10000000;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; i++) {
      cnt[st[i] - '0']++;
    }
    for (int i = 0; i < 10; i++) {
      t = k;
      ans = 0;
      strcpy(ss, st);
      t -= cnt[i];
      if (t <= 0) {
        Min = 0;
        strcpy(Minstr, st);
        break;
      } else {
        for (int l = i - 1, r = i + 1; t; l--, r++) {
          if (t && r < 10 && cnt[r]) {
            tmp = (cnt[r] % t && cnt[r] < t ? cnt[r] : t);
            t -= tmp;
            ans += tmp * (r - i);
            for (int j = 0; j < n && tmp; j++) {
              if ((ss[j] - '0') == r) {
                ss[j] = i + '0';
                tmp--;
              }
            }
          }
          if (t && l >= 0 && cnt[l]) {
            tmp = (cnt[l] % t && cnt[l] < t ? cnt[l] : t);
            t -= tmp;
            ans += tmp * (i - l);
            for (int j = n - 1; j >= 0 && tmp; j--)
              if ((ss[j] - '0') == l) {
                ss[j] = i + '0';
                tmp--;
              }
          }
        }
      }
      if (Min > ans) {
        strcpy(Minstr, ss);
        Min = ans;
      } else if (Min == ans)
        if (strcmp(Minstr, ss) > 0) strcpy(Minstr, ss);
    }
    printf("%d\n%s\n", Min, Minstr);
  }
  return 0;
}
