#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
char str[N], s[N], hehe[N];
int num[10], n, k, cnt, tmin, ans = 1e9;
int main() {
  scanf("%d %d", &n, &k);
  scanf("%s", s);
  for (int i = 0; s[i]; i++) num[s[i] - '0']++;
  for (int dst = 0; dst < 10; dst++) {
    cnt = num[dst];
    tmin = 0;
    memcpy(str, s, sizeof s);
    for (int d = 1; d < 10 && cnt < k; d++) {
      if ((dst + d) < 10) {
        int s = dst + d;
        int e = dst;
        for (int i = 0; i < n && cnt < k; i++) {
          if (str[i] - '0' == s) {
            str[i] = e + '0';
            cnt++;
            tmin = tmin + d;
          }
        }
      }
      if ((dst - d) >= 0) {
        int s = dst - d;
        int e = dst;
        for (int i = n - 1; i >= 0 && cnt < k; i--) {
          if (str[i] - '0' == s) {
            str[i] = e + '0';
            cnt++;
            tmin = tmin + d;
          }
        }
      }
    }
    if (tmin < ans) {
      ans = tmin;
      strcpy(hehe, str);
    } else if (tmin == ans && strcmp(hehe, str) > 0)
      strcpy(hehe, str);
  }
  printf("%d\n", ans);
  printf("%s\n", hehe);
  return 0;
}
