#include <bits/stdc++.h>
using namespace std;
const long long LINF = ~(((long long)0x1) << 63) / 2;
const int INF = 0X3F3F3F3F;
const double eps = 1e-7;
int num[10];
int ok[10];
int main() {
  int n, k, i, j, v;
  string s, ans, now, ss;
  cin >> n >> v;
  cin >> s;
  for (i = 0; i < n; i++) num[s[i] - '0']++;
  int minvalue = INF;
  for (i = 0; i < 10; i++) {
    memset(ok, 0, sizeof(ok));
    int now = v, last = -1;
    now -= num[i];
    ok[i] = 1;
    last = i;
    for (j = 1; j < 10 && now > 0; j++) {
      if (i - j >= 0) {
        now -= num[i - j];
        ok[i - j] = 1;
      }
      if (now <= 0) {
        last = i - j;
        now += num[last];
        break;
      }
      if (i + j < 10) {
        now -= num[i + j];
        ok[i + j] = 1;
      }
      if (now <= 0) {
        last = i + j;
        now += num[last];
        break;
      }
    }
    if (last == i) now += num[i];
    int value = 0;
    ans = "";
    for (j = 0; j < n; j++)
      if (ok[s[j] - '0'] && s[j] - '0' != last)
        ans += i + '0', value += abs(s[j] - '0' - i);
      else
        ans += s[j];
    if (last >= i) {
      for (j = 0; j < n && now > 0; j++)
        if (ans[j] == last + '0')
          ans[j] = i + '0', value += abs(ans[j] - '0' - last), now--;
    } else {
      for (j = n; j >= 0 && now > 0; j--)
        if (ans[j] == last + '0')
          ans[j] = i + '0', value += abs(ans[j] - '0' - last), now--;
    }
    if (value < minvalue) {
      minvalue = value;
      ss = ans;
    } else if (value == minvalue && ans < ss)
      ss = ans;
    memset(ok, 0, sizeof(ok));
    now = v, last = -1;
    now -= num[i];
    ok[i] = 1;
    last = i;
    for (j = 1; j < 10 && now > 0; j++) {
      if (i + j < 10) {
        now -= num[i + j];
        ok[i + j] = 1;
      }
      if (now <= 0) {
        last = i + j;
        now += num[last];
        break;
      }
      if (i - j >= 0) {
        now -= num[i - j];
        ok[i - j] = 1;
      }
      if (now <= 0) {
        last = i - j;
        now += num[last];
        break;
      }
    }
    if (last == i) now += num[i];
    value = 0;
    ans = "";
    for (j = 0; j < n; j++)
      if (ok[s[j] - '0'] && s[j] - '0' != last)
        ans += i + '0', value += abs(s[j] - '0' - i);
      else
        ans += s[j];
    if (last >= i) {
      for (j = 0; j < n && now > 0; j++)
        if (ans[j] == last + '0')
          ans[j] = i + '0', value += abs(ans[j] - '0' - last), now--;
    } else {
      for (j = n; j >= 0 && now > 0; j--)
        if (ans[j] == last + '0')
          ans[j] = i + '0', value += abs(ans[j] - '0' - last), now--;
    }
    if (value < minvalue) {
      minvalue = value;
      ss = ans;
    } else if (value == minvalue && ans < ss)
      ss = ans;
  }
  cout << minvalue << endl;
  cout << ss << endl;
  return 0;
}
