#include <bits/stdc++.h>
using namespace std;
int n, k;
string s, bs = "";
int vis[20], vis2[20];
int ans[20];
int minn = 214700000, pos;
int main() {
  cin >> n >> k;
  cin >> s;
  for (auto c : s) vis[c - '0']++;
  int cnt = 0;
  for (int i = 0; i <= 9; i++) {
    memset(vis2, 0, sizeof(vis2));
    cnt = 0;
    for (int j = 0; j <= 9; j++) {
      vis2[abs(i - j)] += vis[j];
    }
    for (int j = 0; j <= 9; j++) {
      if (cnt + vis2[j] <= k) {
        ans[i] += vis2[j] * j;
        cnt += vis2[j];
      } else {
        ans[i] += (k - cnt) * j;
        break;
      }
    }
  }
  for (int i = 0; i <= 9; i++) {
    if (ans[i] < minn) minn = ans[i];
  }
  if (minn == 0) {
    cout << 0 << endl << s;
    return 0;
  }
  string temp = s;
  for (int m = 0; m <= 9; m++) {
    if (minn == ans[m]) {
      pos = m;
      cnt = vis[pos];
      s = temp;
      bool jug = false;
      for (int i = 1; i <= 9; i++) {
        for (int j = pos + 1; j <= 9; j++) {
          if (j - pos == i) {
            for (int l = 0; l <= s.size() - 1; l++) {
              if (s[l] == j + '0') {
                cnt++;
                s[l] = (char)(pos + '0');
              }
              if (cnt >= k) {
                if (bs.size() == 0)
                  bs = s;
                else if (s < bs)
                  bs = s;
                jug = true;
                break;
              }
            }
            if (jug) break;
          }
          if (j - pos == -i) {
            for (int l = s.size() - 1; l >= 0; l--) {
              if (s[l] == j + '0') {
                cnt++;
                s[l] = (char)(pos + '0');
              }
              if (cnt >= k) {
                if (bs.size() == 0)
                  bs = s;
                else if (s < bs)
                  bs = s;
                jug = true;
                break;
              }
            }
            if (jug) break;
          }
        }
        if (jug) break;
        for (int j = pos - 1; j >= 0; j--) {
          if (j - pos == i) {
            for (int l = 0; l <= s.size() - 1; l++) {
              if (s[l] == j + '0') {
                cnt++;
                s[l] = (char)(pos + '0');
              }
              if (cnt >= k) {
                if (bs.size() == 0)
                  bs = s;
                else if (s < bs)
                  bs = s;
                jug = true;
                break;
              }
            }
            if (jug) break;
          }
          if (j - pos == -i) {
            for (int l = s.size() - 1; l >= 0; l--) {
              if (s[l] == j + '0') {
                cnt++;
                s[l] = (char)(pos + '0');
              }
              if (cnt >= k) {
                if (bs.size() == 0)
                  bs = s;
                else if (s < bs)
                  bs = s;
                jug = true;
                break;
              }
            }
            if (jug) break;
          }
        }
        if (jug) break;
      }
    }
  }
  cout << minn << endl << bs;
  return 0;
}
