#include <bits/stdc++.h>
using namespace std;
int str[10009], str1[10009];
int main(void) {
  int n, k;
  scanf("%d%d", &n, &k);
  getchar();
  for (int i = 0; i < n; i++) {
    char cc;
    scanf("%c", &cc);
    str[i] = cc - '0';
  }
  memcpy(str1, str, sizeof(str));
  sort(str, str + n);
  int anc[10];
  memset(anc, 1e6, sizeof(anc));
  for (int i = 0; i < 10; i++) {
    bool hk = false;
    int key = 0;
    for (; key < n; key++)
      if (str[key] == i) {
        hk = true;
        break;
      }
    int l, r;
    l = r = key;
    for (int x = n - 1; x >= 0; x--)
      if (str[x] == i) {
        hk = true;
        r = x;
        break;
      }
    if (hk) {
      anc[i] = 0;
      while (l >= 0 || r < n) {
        if (r - l + 1 >= k) break;
        if ((r + 1 < n && l - 1 >= 0 && str[r + 1] - i < i - str[l - 1]) ||
            (r + 1 < n && l - 1 < 0)) {
          if (r + 1 < n) {
            r++;
            anc[i] += str[r] - i;
          }
        } else {
          if (l - 1 >= 0) {
            l--;
            anc[i] += i - str[l];
          }
        }
      }
    }
  }
  int mins = 1000000, log = -1;
  for (int i = 0; i < 10; i++) {
    if (anc[i] < mins) {
      mins = anc[i];
      log = i;
    } else if (anc[i] == mins) {
      bool breakout = false;
      for (int ij = 1; ij < 10; ij++) {
        for (int j = 0; j < n; j++) {
          if (str1[j] == log + ij) breakout = true;
          if (breakout) break;
          if (str1[j] == i + ij) {
            log = i;
            breakout = true;
          }
          if (breakout) break;
        }
        if (breakout) break;
      }
    }
  }
  printf("%d\n", mins);
  for (int k = 1;; k++) {
    if (mins <= 0) break;
    if (log + k <= 9)
      for (int i = 0; i < n; i++) {
        if (str1[i] == log + k) {
          str1[i] = log;
          mins -= k;
          if (mins <= 0) goto l1;
        }
      }
    if (log - k >= 0)
      for (int i = n - 1; i >= 0; i--) {
        if (str1[i] == log - k) {
          str1[i] = log;
          mins -= k;
          if (mins <= 0) goto l1;
        }
      }
  }
l1:
  for (int i = 0; i < n; i++) printf("%d", str1[i]);
  printf("\n");
  return 0;
}
