#include <bits/stdc++.h>
using namespace std;
const int INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-9;
int bit_count(int first) {
  return first == 0 ? 0 : 1 + bit_count(first & (first - 1));
}
inline int low_bit(int first) { return first & -first; }
inline int sign(double first) {
  return first < -EPS ? -1 : first > EPS ? 1 : 0;
}
inline int sign(int first) { return (first > 0) - (first < 0); }
template <class T>
void chmin(T &t, T f) {
  if (t > f) t = f;
}
template <class T>
void chmax(T &t, T f) {
  if (t < f) t = f;
}
int gcd(int a, int b) {
  while (b) {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int nextComb(int first) {
  int smallest = first & -first;
  int ripple = first + smallest;
  int ones = first ^ ripple;
  ones = (ones >> 2) / smallest;
  return ripple | ones;
}
inline int getint() {
  int a;
  return scanf("%d", &a) ? a : (fprintf(stderr, "trying to read\n"), -1);
}
inline double getdouble() {
  double a;
  return scanf("%lf", &a) ? a : (fprintf(stderr, "trying to read\n"), -1.0);
}
void myCode() {
  int n = getint(), k = getint();
  string s;
  cin >> s;
  vector<int> a(10, 0);
  vector<vector<int> > b(10, vector<int>(10, 0));
  for (int i = (int)0; i < (int)n; ++i) a[s[i] - '0']++;
  string t;
  int ret = INF;
  string retS;
  for (int i = (int)0; i < (int)10; ++i) {
    int togo = max(0, k - a[i]);
    int cost = 0;
    b[i][i] = a[i] - togo;
    for (int j = (int)1; j < (int)10; ++j) {
      if (i + j < 10) {
        int d = min(togo, a[i + j]);
        togo -= d;
        cost += j * d;
        b[i][i + j] = d;
      }
      if (i - j >= 0) {
        int d = min(togo, a[i - j]);
        togo -= d;
        cost += j * d;
        b[i][i - j] = d;
      }
    }
    if (cost < ret) {
      ret = cost;
      retS = string(s);
      for (int i = (int)0; i < (int)((int)(retS).size()); ++i) retS[i] = '9';
    }
    if (cost == ret) {
      t = string(s);
      for (int j = (int)0; j < (int)((int)(t).size()); ++j)
        if (t[j] - '0' >= i && b[i][t[j] - '0']) {
          --b[i][t[j] - '0'];
          t[j] = i + '0';
        }
      for (int j = (int)(((int)(t).size())) - 1; j >= 0; --j)
        if (t[j] - '0' < i && b[i][t[j] - '0']) {
          --b[i][t[j] - '0'];
          t[j] = i + '0';
        }
      if (t < retS) retS = t;
    }
  }
  printf("%d\n%s\n", ret, retS.c_str());
}
int main() {
  srand(time(NULL));
  myCode();
  return 0;
}
