#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000 + 5;
char s[MAXN], str[MAXN], res[MAXN];
int cnt[11];
int n, k, l;
int main() {
  cin >> n >> k >> s;
  l = strlen(s);
  for (int i = 0; s[i]; i++) {
    cnt[s[i] - '0']++;
  }
  int ans = (1 << 30) - 1;
  for (int i = 0; i <= 9; i++) {
    int tot = cnt[i], sum = 0;
    strcpy(str, s);
    for (int j = 1; j <= 9 && tot < k; j++) {
      if (i + j < 10) {
        for (int tmp = 0; tmp < n && tot < k; tmp++) {
          if (str[tmp] - '0' == i + j) {
            str[tmp] = i + '0';
            tot++;
            sum += j;
          }
        }
      }
      if (i - j >= 0) {
        for (int tmp = n - 1; tmp >= 0 && tot < k; tmp--) {
          if (str[tmp] - '0' == i - j) {
            str[tmp] = i + '0';
            tot++;
            sum += j;
          }
        }
      }
    }
    if (sum < ans || sum == ans && strcmp(res, str) > 0) {
      ans = sum;
      strcpy(res, str);
    }
  }
  cout << ans << endl << res << endl;
  return 0;
}
