#include <bits/stdc++.h>
using namespace std;
int n, k, f[10], mn = 1 << 29;
string str, res;
string calc(int b) {
  int rem = k - f[b];
  vector<int> F(f, f + 10);
  int l = b - 1, r = b + 1;
  int cost = 0;
  vector<int> change(10, 0);
  while (rem) {
    if (r < 10 && !F[r]) {
      ++r;
      continue;
    }
    if (l >= 0 && !F[l]) {
      --l;
      continue;
    }
    if (l >= 0 && r < 10) {
      if (r - b <= b - l) {
        cost += r - b;
        ++change[r];
        --F[r];
      } else {
        cost += b - l;
        ++change[l];
        --F[l];
      }
    } else if (l >= 0) {
      --F[l];
      ++change[l];
      cost += b - l;
    } else {
      --F[r];
      ++change[r];
      cost += r - b;
    }
    --rem;
  }
  if (cost > mn) return string(n, '9');
  if (cost < mn) res = string(n, '9');
  mn = min(mn, cost);
  string ret = str;
  for (int j = 9; j > b; --j)
    for (int i = 0; change[j] && i < ret.size(); ++i)
      if (ret[i] - '0' == j) {
        ret[i] = b + '0';
        --change[j];
      }
  for (int j = 0; j < b; ++j)
    for (int i = ret.size() - 1; change[j] && i >= 0; --i)
      if (ret[i] - '0' == j) {
        ret[i] = b + '0';
        --change[j];
      }
  return ret;
}
int main() {
  cin >> n >> k >> str;
  for (int i = 0; i < str.size(); ++i) {
    ++f[str[i] - '0'];
    if (f[str[i] - '0'] == k) {
      cout << 0 << endl << str << endl;
      return 0;
    }
  }
  res = string(n, '9');
  for (int i = 0; i < 10; ++i) res = min(res, calc(i));
  cout << mn << endl;
  cout << res << endl;
  return 0;
}
