#include <bits/stdc++.h>
using namespace std;
int n, k, cnt, sum, ans = 1e9, minn, num[20];
char s[100010], S[100010], str[100010];
int main() {
  scanf("%d%d", &n, &k);
  scanf("%s", s);
  for (int i = 0; s[i]; i++) num[s[i] - '0']++;
  for (int i = 0; i <= 9; i++) {
    memcpy(str, s, sizeof(s));
    cnt = num[i];
    minn = 0;
    for (int j = 1; j <= 9 && cnt < k; j++) {
      if (i + j < 10) {
        sum = i + j;
        for (int l = 0; l < n && cnt < k; l++) {
          if (str[l] - '0' == sum) {
            str[l] = i + '0';
            cnt++;
            minn += j;
          }
        }
      }
      if (i - j >= 0) {
        sum = i - j;
        for (int l = n - 1; l >= 0 && cnt < k; l--) {
          if (str[l] - '0' == sum) {
            str[l] = i + '0';
            cnt++;
            minn += j;
          }
        }
      }
    }
    if (minn < ans) {
      ans = minn;
      strcpy(S, str);
    } else if (minn == ans && strcmp(S, str) > 0)
      strcpy(S, str);
  }
  printf("%d\n", ans);
  printf("%s", S);
}
