#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e4 + 5;
int n, k, sol = 1e9, t[MAX][5];
char e[MAX], h[MAX], s[MAX];
pair<int, int> a[MAX];
void relax(int ans, char* h) {
  if (ans < sol) {
    sol = ans;
    strcpy(s + 1, h + 1);
  }
  if (ans == sol && strcmp(h + 1, s + 1) == -1) strcpy(s + 1, h + 1);
}
void check(int d) {
  int cnt = k, cost = 0;
  for (int i = 1; i <= n; i++) {
    h[i] = e[i];
    if (e[i] == d) cnt--;
  }
  if (cnt <= 0) {
    relax(cost, h);
    return;
  }
  for (int k = 1; k < 10; k++) {
    if (t[k][0] == 0) continue;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= t[k][0]; j++) {
        int d1 = t[k][j] + '0';
        if (h[i] == d1) {
          if (d1 > d) {
            cost += k;
            cnt--;
            h[i] = d;
          }
          break;
        }
      }
      if (cnt == 0) break;
    }
    if (cnt == 0) break;
    for (int i = n; i > 0; i--) {
      for (int j = 1; j <= t[k][0]; j++) {
        int d1 = t[k][j] + '0';
        if (h[i] == d1) {
          if (d1 < d) {
            cost += k;
            cnt--;
            h[i] = d;
          }
          break;
        }
      }
      if (cnt == 0) break;
    }
    if (cnt == 0) break;
  }
  if (cnt == 0) relax(cost, h);
}
int main() {
  scanf("%d%d\n", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%c", &e[i]);
    s[i] = '9';
  }
  for (int d = 0; d < 10; d++) {
    for (int i = 0; i < 10; i++) {
      a[i].first = abs(d - i);
      a[i].second = i;
    }
    sort(a, a + 10);
    for (int i = 0; i < 10; i++) t[i][0] = 0;
    for (int i = 0; i < 10; i++)
      t[a[i].first][++t[a[i].first][0]] = a[i].second;
    check(d + '0');
  }
  printf("%d\n%s\n", sol, s + 1);
  return 0;
}
