#include <bits/stdc++.h>
using namespace std;
string s, final, tmp;
int num[10], ans, n, m;
vector<int> p[10];
void solve(int tar) {
  int cnt = num[tar], res = 0, delta = 1, number;
  tmp = s;
  while (cnt < m) {
    number = tar + delta;
    if (number < 10) {
      for (int i = 0; i < p[number].size() && cnt < m; i++, cnt++)
        tmp[p[number][i]] = tar + '0', res += delta;
    }
    number = tar - delta;
    if (number >= 0) {
      for (int i = p[number].size() - 1; i >= 0 && cnt < m; i--, cnt++)
        tmp[p[number][i]] = tar + '0', res += delta;
    }
    delta++;
  }
  if (res < ans)
    ans = res, final = tmp;
  else if (res == ans && tmp < final)
    final = tmp;
}
int main() {
  while (cin >> n >> m >> s) {
    memset(num, 0, sizeof(num));
    for (int i = 0; i < 10; i++) p[i].clear();
    for (int i = 0; i < n; i++) num[s[i] - '0']++, p[s[i] - '0'].push_back(i);
    ans = 0x3f3f3f3f;
    final = s;
    for (int i = 0; i < n; i++) final[i] = '9';
    for (int tar = 0; tar < 10; tar++) {
      if (num[tar] >= m) {
        ans = 0, final = s;
        break;
      } else
        solve(tar);
    }
    cout << ans << endl;
    cout << final << endl;
  }
  return 0;
}
