#include <bits/stdc++.h>
using namespace std;
int n, k, ans, sum, nann;
const int MAXN = 10000;
const int INF = 0x3f3f3f3f;
int bac[11], _bac[11];
int a[MAXN + 10], b[MAXN + 10], c[MAXN + 10];
inline int abs(int x) { return x < 0 ? -x : x; }
inline int solve1(int x) {
  for (int i = 0; i <= 9; ++i) _bac[i] = bac[i];
  int tmp = 0;
  for (int i = 2; _bac[x] < k; ++i) {
    int a = (i & 1) ? -(i >> 1) : (i >> 1);
    a += x;
    if (a < 0 || a > 9) continue;
    if (bac[a] >= k - _bac[x]) {
      tmp += (k - _bac[x]) * abs(x - a);
      _bac[a] = _bac[a] - (k - _bac[x]);
      _bac[x] = k;
      break;
    } else {
      tmp += _bac[a] * abs(x - a);
      _bac[x] += _bac[a];
      _bac[a] = 0;
    }
  }
  return tmp;
}
inline void solve2(int x, int *p) {
  for (int i = 1; i <= n; ++i) p[i] = a[i];
  for (int i = 1; i <= n; ++i) {
    if (a[i] > x && _bac[a[i]] < bac[a[i]]) {
      p[i] = x;
      _bac[a[i]]++;
    }
  }
  for (int i = n; i >= 1; --i) {
    if (a[i] < x && _bac[a[i]] < bac[a[i]]) {
      p[i] = x;
      _bac[a[i]]++;
    }
  }
}
inline bool comp(int *a, int *b) {
  for (int i = 1; i <= n; ++i) {
    if (a[i] < b[i]) return 0;
    if (a[i] > b[i]) return 1;
  }
  return 0;
}
int main() {
  ans = INF;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%1d", &a[i]);
    bac[a[i]]++;
    b[i] = INF;
  }
  for (int i = 0; i <= 9; ++i) {
    sum = solve1(i);
    if (ans > sum) {
      ans = sum;
      solve2(i, b);
    } else if (ans == sum) {
      solve2(i, c);
      if (comp(b, c)) {
        for (int j = 1; j <= n; ++j) b[j] = c[j];
      }
    }
  }
  printf("%d\n", ans);
  for (int i = 1; i <= n; ++i) putchar(b[i] ^ 48);
  putchar('\n');
  return 0;
}
