#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int main() {
  ios::sync_with_stdio(false);
  int n, k, mn = 1e9, c[10] = {0}, mnArray[10] = {0};
  string s;
  cin >> n >> k >> s;
  for (int i = (0); i < (n); i++) c[s[i] - '0']++;
  for (int digit = (0); digit < (10); digit++) {
    int cnt = 0, rem = k - c[digit];
    int i = digit - 1, j = digit + 1;
    while ((i >= 0 || j <= 9) && rem > 0) {
      if (j <= 9) {
        if (c[j] >= rem)
          cnt += (j - digit) * rem, rem = 0;
        else
          cnt += (j - digit) * c[j], rem -= c[j];
        j++;
      }
      if (i >= 0) {
        if (c[i] >= rem)
          cnt += (digit - i) * rem, rem = 0;
        else
          cnt += (digit - i) * c[i], rem -= c[i];
        i--;
      }
    }
    mnArray[digit] = cnt;
    if (cnt < mn) mn = cnt;
  }
  vector<string> res;
  int K = k;
  for (int digit = (0); digit < (10); digit++) {
    if (mnArray[digit] == mn) {
      string r = s;
      int rem = K - c[digit];
      if (rem > 0) {
        int i = digit - 1, j = digit + 1;
        while ((i >= 0 || j <= 9) && rem > 0) {
          if (j <= 9) {
            for (int k = (0); k < (n); k++) {
              if (r[k] == j + '0' && rem) r[k] = digit + '0', rem--;
            }
            j++;
          }
          if (i >= 0) {
            for (int k = (n - 1); k >= (0); k--) {
              if (r[k] == i + '0' && rem) r[k] = digit + '0', rem--;
            }
            i--;
          }
        }
      }
      res.push_back(r);
    }
  }
  sort((res).begin(), (res).end());
  cout << mn << endl;
  cout << res[0] << endl;
  return 0;
}
