#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9 + 7;
const long long INF = 1e18 + 5;
const long long mxn = 1e6 + 5;
const int mod = 1e9 + 7, pa = 1e6 + 7;
long long n, a[555555], u[555555], mx = 0, l[mxn], pr[mxn];
long long c[555555], b[555555], p[555555];
vector<int> v[mxn];
int main() {
  int n, k;
  cin >> n >> k;
  string second;
  cin >> second;
  for (int i = 0; i < second.size(); i++) c[second[i] - '0']++;
  string h = second, ss = second;
  h += '9';
  int mn = 1e9, id = 0;
  for (int i = 0; i <= 9; i++) {
    long long x = k - c[i];
    int y = 0;
    if (x <= 0 && mn > x) mn = 0, id = i, l[i] = 0;
    if (x < 0) x = 0;
    vector<pair<int, int> > v;
    for (int j = 0; j <= 9; j++) v.push_back(make_pair(abs(i - j), j));
    sort(v.begin(), v.end());
    for (int j = 1; j < v.size(); j++) {
      y += min(x, c[v[j].second]) * v[j].first, x -= min(x, c[v[j].second]);
    }
    if (mn > y) mn = y, id = i;
    l[i] = y;
  }
  cout << mn << endl;
  if (mn == 0) return cout << second, 0;
  for (int jj = 0; jj <= 9; jj++) {
    id = jj;
    second = ss;
    if (l[id] != mn) continue;
    vector<int> v[55];
    if (mn == 0) return cout << second, 0;
    int x = max(0ll, k - c[id]);
    for (int i = 0; i < n; i++)
      if (id != second[i] - '0') v[abs(second[i] - '0' - id)].push_back(i);
    int ii = id;
    id = 0;
    int y = 0;
    for (int i = 0; i < n; i++) b[i] = second[i] - '0';
    y = mn;
    for (int i = 1; i <= 10; i++) {
      if (y - v[i].size() >= 0)
        id = i, y -= v[i].size(), p[i] = v[i].size();
      else
        p[i] = y / i, y = 0;
    }
    for (int i = 1; i <= 10; i++) {
      for (int j = 0; j < v[i].size(); j++)
        if (x > 0 && b[v[i][j]] > ii && p[i] > 0)
          x--, second[v[i][j]] = ii + '0', p[i]--;
      for (int j = v[i].size() - 1; j >= 0; j--)
        if (x > 0 && p[i] > 0 && b[v[i][j]] < ii)
          x--, p[i]--, second[v[i][j]] = ii + '0';
    }
    if (h.size() > second.size()) h = second;
    if (h > second) h = second;
    second = ss;
  }
  cout << h;
  return 0;
}
