#include <bits/stdc++.h>
using namespace std;
int n, k;
int c[32];
int cost[32];
int totcost[32];
char s[10010];
vector<int> ktore[32];
vector<int> rozwaz;
vector<string> minstring;
string ss[10];
int main() {
  scanf("%d %d", &n, &k);
  scanf("%s", s);
  for (int i = 0; i < n; i++) c[s[i] - '0']++;
  int cur = 0;
  int ile = 0;
  int dol = 1;
  for (int i = 0; i <= 9; i++) {
    dol = 0;
    cur = 1;
    ile = c[i];
    cost[i] = 0;
    ktore[i].push_back(i);
    while (ile < k) {
      if (dol) {
        dol = 0;
        if (i - cur >= 0) {
          if (ile + c[i - cur] <= k)
            cost[i] += cur * c[i - cur];
          else
            cost[i] += (k - ile) * cur;
          ile += c[i - cur];
          ktore[i].push_back(i - cur);
        }
        cur++;
      } else {
        dol = 1;
        if (i + cur <= 9) {
          if (ile + c[i + cur] <= k)
            cost[i] += (cur)*c[i + cur];
          else
            cost[i] += (k - ile) * (cur);
          ile += c[i + cur];
          ktore[i].push_back(i + cur);
        }
      }
    }
  }
  int minn = 100000000;
  for (int i = 0; i <= 9; i++) minn = ((cost[i]) < (minn) ? (cost[i]) : (minn));
  printf("%d\n", minn);
  for (int i = 0; i <= 9; i++) {
    if (cost[i] == minn) {
      rozwaz.push_back(i);
    }
  }
  int il;
  for (int t = 0; t < rozwaz.size(); t++) {
    int i = rozwaz[t];
    ss[i] = s;
    il = c[i];
    for (int j = 1; j < ktore[i].size(); j++) {
      if (ktore[i][j] < i) {
        for (int q = (ss[i].size() - 1); q >= 0 && il < k; q--) {
          if ((ss[i][q]) == (ktore[i][j] + '0')) {
            il++;
            ss[i][q] = i + '0';
          }
        }
      } else {
        for (int q = 0; q < ss[i].size() && il < k; q++) {
          if (ss[i][q] == (ktore[i][j] + '0')) {
            il++;
            ss[i][q] = i + '0';
          }
        }
      }
    }
    minstring.push_back(ss[i]);
  }
  sort(minstring.begin(), minstring.end());
  cout << minstring[0] << "\n";
  return 0;
}
