#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
int n, k, len, tot, a[N], ans = 1e8, vis[11], Min, num[11];
char s[N], anss[N], str[N];
int main() {
  cin >> n >> k >> s;
  len = strlen(s);
  for (int i = 0; i < len; i++) num[s[i] - '0']++;
  for (int i = 0; i <= 9; i++) {
    int tot = num[i], sum = 0;
    memcpy(str, s, sizeof(s));
    for (int j = 1; j <= 9 && tot < k; j++) {
      int x = i + j, y = i - j;
      if (x < 10) {
        for (int l = 0; l < len && tot < k; l++)
          if (str[l] - '0' == x) {
            str[l] = i + '0';
            tot++;
            sum += j;
          }
      }
      if (y >= 0) {
        for (int l = len - 1; l >= 0 && tot < k; l--) {
          if (str[l] - '0' == y) {
            str[l] = i + '0';
            tot++;
            sum += j;
          }
        }
      }
    }
    if (sum < ans) {
      ans = sum;
      strcpy(anss, str);
    } else {
      if (sum == ans && strcmp(anss, str) > 0) strcpy(anss, str);
    }
  }
  cout << ans << endl << anss;
  return 0;
}
