#include <bits/stdc++.h>
using namespace std;
int n, k;
char s[22222], str[22222], anss[22222];
int ans = 1e9;
int num[555];
int main() {
  scanf("%d%d", &n, &k);
  cin >> s;
  for (int i = 0; i < n; 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 < n && tot < k; l++)
          if (str[l] - '0' == x) {
            str[l] = '0' + i;
            tot++;
            sum += j;
          }
      }
      if (y >= 0) {
        for (int l = n - 1; l >= 0 && tot < k; l--)
          if (str[l] - '0' == y) {
            str[l] = '0' + i;
            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 << endl;
}
