#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k, min = 100500, c = 0;
  string st, s, str, ss;
  cin >> n >> k >> st;
  for (int i = 0; i < n; i++) ss += '9';
  for (int i = 0; i < 10; i++) {
    s = st;
    c = 0;
    int kol = count(s.begin(), s.end(), i + '0');
    for (int d = 1; d <= 9; d++) {
      if (i + d < 10)
        for (int j = 0; j < s.size() && kol < k; j++)
          if (s[j] == i + d + '0') {
            kol++;
            c += d;
            s[j] = i + '0';
          }
      if (i - d >= 0)
        for (int j = s.size() - 1; j >= 0 && kol < k; j--)
          if (s[j] == i - d + '0') {
            kol++;
            c += d;
            s[j] = i + '0';
          }
    }
    if (c < min) {
      min = c;
      ss = s;
    } else if (c == min && s < ss) {
      min = c;
      ss = s;
    }
  }
  cout << min << endl << ss;
  return 0;
}
