#include <bits/stdc++.h>
using namespace std;
int main() {
  int i, j, k, n, p, q;
  string st;
  cin >> n >> k >> st;
  int l = st.size();
  int cnt[10];
  memset(cnt, 0, sizeof(cnt));
  for (i = 0; i < l; i++) cnt[st[i] - '0']++;
  int ch, cst = 2000000000, tmp;
  string ans = "", tmpst;
  int mm[10];
  for (i = 0; i <= 9; i++) {
    memset(mm, 0, sizeof(mm));
    j = cnt[i];
    tmp = 0;
    for (p = 1; p <= 9 && j < k; p++) {
      if (i + p <= 9) {
        if (j + cnt[i + p] <= k) {
          mm[i + p] = cnt[i + p];
          j += cnt[i + p];
          tmp += p * mm[i + p];
        } else {
          mm[i + p] = k - j;
          j = k;
          tmp += p * mm[i + p];
        }
        if (j == k) break;
      }
      if (i - p >= 0) {
        if (j + cnt[i - p] <= k) {
          mm[i - p] = cnt[i - p];
          j += cnt[i - p];
          tmp += p * mm[i - p];
        } else {
          mm[i - p] = k - j;
          j = k;
          tmp += p * mm[i - p];
        }
        if (j == k) break;
      }
    }
    tmpst = "";
    int tmpcnt[10];
    memset(tmpcnt, 0, sizeof(tmpcnt));
    for (p = 0; p < l; p++) {
      tmpcnt[st[p] - '0']++;
      if (st[p] - '0' == i)
        tmpst += st[p];
      else if (st[p] - '0' < i) {
        if (tmpcnt[st[p] - '0'] + mm[st[p] - '0'] > cnt[st[p] - '0'])
          tmpst += i + '0';
        else
          tmpst += st[p];
      } else {
        if (mm[st[p] - '0']) {
          tmpst += i + '0';
          mm[st[p] - '0']--;
        } else
          tmpst += st[p];
      }
    }
    if (tmp < cst) {
      cst = tmp;
      ans = tmpst;
    } else if (tmp == cst) {
      if (tmpst < ans) ans = tmpst;
    }
  }
  cout << cst << endl << ans;
  return 0;
}
