#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 5;
int n, k, a[15], b[maxn];
string s;
int compt(int x, int num, int flag) {
  int sum = 0;
  for (int i = 1; i <= 9 && num > 0; i++) {
    if (x + i <= 9 && a[x + i]) {
      if (num >= a[x + i]) {
        if (flag == 2) b[x + i] = a[x + i];
        sum += i * a[x + i];
        num -= a[x + i];
      } else {
        if (flag == 2) b[x + i] = num;
        sum += i * num;
        num = 0;
      }
    }
    if (x - i >= 0 && a[x - i]) {
      if (num >= a[x - i]) {
        if (flag == 2) b[x - i] = a[x - i];
        sum += i * a[x - i];
        num -= a[x - i];
      } else {
        if (flag == 2) b[x - i] = num;
        sum += i * num;
        num = 0;
      }
    }
  }
  return sum;
}
string solve(int p, string s) {
  compt(p, k - a[p], 2);
  for (int i = 0; i < n; i++) {
    int cur = s[i] - '0';
    if (b[cur] && cur > p) {
      b[cur]--;
      s[i] = p + '0';
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    int cur = s[i] - '0';
    if (b[cur] && cur < p) {
      b[cur]--;
      s[i] = p + '0';
    }
  }
  return s;
}
int main() {
  cin >> n >> k >> s;
  for (int i = 0; i < n; i++) a[s[i] - '0']++;
  int sum = 1e9, p;
  for (int i = 0; i <= 9; i++)
    if (compt(i, k - a[i], 1) < sum) {
      sum = compt(i, k - a[i], 1);
      p = i;
    }
  cout << sum << endl;
  string tmp = solve(p, s);
  for (int i = 0; i <= 9; i++) {
    if (compt(i, k - a[i], 1) == sum) {
      string tt = solve(i, s);
      if (tmp > tt) tmp = tt;
    }
  }
  cout << tmp << endl;
}
