#include <bits/stdc++.h>
using namespace std;
void File() {
  freopen("output.txt", "w", stdout);
  freopen("input.txt", "r", stdin);
}
void yAsEr_HaFiz() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[] = {1, -1, 0, 0, -1, 1, 1, -1};
int const N = 2e5 + 9, MOD = 1e9 + 7, oo = 1e9 + 7;
int n, k;
int f[N], m = oo, ff[20];
vector<int> v;
string str, newone;
vector<string> res;
void getnewone(int i) {
  newone = str;
  int index;
  for (int j = 0; j < v.size(); j++) {
    if (v[j] < i) {
      for (int k = 0; k < newone.size(); k++) {
        if (newone[k] == v[j] + '0') index = k;
      }
      newone[index] = i + '0';
    } else {
      for (int k = 0; k < newone.size(); k++) {
        if (newone[k] == v[j] + '0') {
          index = k;
          break;
        }
      }
      newone[index] = i + '0';
    }
  }
}
int getmini(int i, int target) {
  long long s = 0, cnt = 1, l = i - 1, r = i + 1;
  while (target != 0) {
    if (r >= 10 || f[r] == 0)
      ;
    else {
      if (target >= f[r]) {
        target -= f[r];
        s += f[r] * cnt;
        for (int j = 0; j < int(f[r]); j++) v.push_back(r);
      } else {
        s += (long long)target * cnt;
        for (int j = 0; j < int(target); j++) v.push_back(r);
        target -= target;
      }
    }
    if (target == 0) return s;
    if (l < 0 || f[l] == 0)
      ;
    else {
      if (target >= f[l]) {
        target -= f[l];
        s += (long long)f[l] * cnt;
        for (int j = 0; j < int(f[l]); j++) v.push_back(l);
      } else {
        s += (long long)target * cnt;
        for (int j = 0; j < int(target); j++) v.push_back(l);
        target -= target;
      }
    }
    r++;
    l--;
    cnt++;
  }
  return s;
}
int main() {
  cin >> n >> k >> str;
  for (int i = 0; i < int(n); i++) f[str[i] - '0']++;
  for (int i = 0; i < int(10); i++) {
    int target = k - f[i];
    if (target <= 0) return cout << 0 << '\n' << str, 0;
    v.clear();
    int x = getmini(i, target);
    if (x < m) {
      res.clear();
      getnewone(i);
      res.push_back(newone);
      m = x;
    } else if (x == m) {
      getnewone(i);
      res.push_back(newone);
    }
  }
  sort(res.begin(), res.end());
  cout << m << '\n' << res[0];
  return 0;
}
