#include <bits/stdc++.h>
using namespace std;
struct CNT {
  int v, t;
} tz[20];
struct ANS {
  int c;
  string str;
} p[20];
inline bool cmp(const CNT& a, const CNT& b) {
  return a.t > b.t || (a.t == b.t && a.v < b.v);
}
inline bool cmp2(const ANS& a, const ANS& b) {
  return a.c < b.c || (a.c == b.c && a.str < b.str);
}
string st;
int main() {
  int n, ki, tot = 0, cost;
  cin >> n >> ki >> st;
  for (int i = 1; i <= 10; i++) tz[i].v = i - 1;
  for (int i = 0; i < st.size(); i++) tz[st[i] - '0' + 1].t++;
  sort(tz + 1, tz + 11, cmp);
  if (tz[1].t >= ki) {
    cout << '0' << endl;
    cout << st;
    return 0;
  }
  for (int i = 1; tz[i].t > 0 && i <= n; i++) {
    int cr = tz[i].v, k = ki;
    k -= tz[i].t;
    string s = st;
    cost = 0;
    for (int x = 1; k > 0; x++) {
      if (cr + x <= 9) {
        for (int i = 0; k > 0 && i < s.size(); i++)
          if (s[i] - '0' == cr + x) s[i] = cr + '0', k--, cost += x;
      }
      if (cr - x >= 0) {
        for (int i = s.size() - 1; k > 0 && i >= 0; i--)
          if (s[i] - '0' == cr - x) s[i] = cr + '0', k--, cost += x;
      }
    }
    p[++tot] = {cost, s};
  }
  sort(p + 1, p + tot + 1, cmp2);
  cout << p[1].c << endl;
  cout << p[1].str;
  return 0;
}
