#include <bits/stdc++.h>
using namespace std;
int n, k;
char s[11000];
int nu[11000];
int sum[10];
int Min;
int mind;
int Minus[10];
int mr[10];
string str[10];
string anss;
int work(int i) {
  for (int j = 0; j < 10; j++) Minus[j] = 0;
  int ans = 0;
  int l = i - 1, r = i + 1;
  int kk = k - sum[i];
  while (kk > 0) {
    if (r < 10) {
      if (sum[r] >= kk) {
        ans += kk * (r - i);
        Minus[r] = kk;
        break;
      } else {
        kk -= sum[r];
        ans += sum[r] * (r - i);
        Minus[r] = sum[r];
        r++;
      }
    }
    if (l >= 0) {
      if (sum[l] >= kk) {
        ans += kk * (i - l);
        Minus[l] = kk;
        break;
      } else {
        kk -= sum[l];
        ans += sum[l] * (i - l);
        Minus[l] = sum[l];
        l--;
      }
    }
  }
  return ans;
}
void dis(int x) {
  for (int i = 0; i < n; i++) {
    nu[i] = s[i] - '0';
  }
  for (int i = 0; i < n; i++) {
    if (mr[nu[i]] > 0 && nu[i] > x) {
      mr[nu[i]]--;
      nu[i] = x;
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    if (mr[nu[i]] > 0 && nu[i] < x) {
      mr[nu[i]]--;
      nu[i] = x;
    }
  }
  for (int i = 0; i < n; i++) str[x].push_back('0' + nu[i]);
}
int main() {
  do {
    cin >> n >> k;
    cin >> s;
    for (int i = 0; i < 10; i++) sum[i] = 0, Minus[i] = 0;
    for (int i = 0; i < n; i++) {
      nu[i] = s[i] - '0';
      sum[nu[i]]++;
    }
    Min = 900000;
    for (int i = 0; i < 10; i++) {
      int tmp = work(i);
      if (Min > tmp) {
        Min = tmp;
        mind = i;
        for (int j = 0; j < 10; j++) mr[j] = Minus[j];
        dis(i);
        anss = str[i];
      } else if (Min == tmp) {
        Min = tmp;
        mind = i;
        for (int j = 0; j < 10; j++) mr[j] = Minus[j];
        dis(i);
        if (str[i] < anss) {
          anss = str[i];
        }
      }
    }
    cout << Min << endl;
    cout << anss << endl;
  } while (0);
}
