#include <bits/stdc++.h>
using namespace std;
const int maxn = 10050;
const int inf = 0x7fffffff;
string str;
int buf[maxn];
vector<int> sans[10];
int save[300] = {};
string ansstr;
string bk;
int bK;
int main(void) {
  int n, K;
  cin >> n >> K >> str;
  int ans = inf;
  for (int k = ('0'); k <= ('9'); ++k) {
    for (int i = 0; i < (n); ++i) buf[i] = abs(k - str[i]);
    sort(buf, buf + n);
    int res = accumulate(buf, buf + K, 0);
    if (ans > res) ans = res;
    save[k] = res;
  }
  cout << ans << endl;
  for (int i = 0; i < (n); ++i) ansstr.push_back('9');
  bk = str;
  bK = K;
  for (int no = ('0'); no <= ('9'); ++no)
    if (save[no] == ans) {
      K = bK;
      str = bk;
      for (int i = 0; i < (10); ++i) sans[i].clear();
      for (int i = 0; i < (n); ++i) {
        if (str[i] >= no)
          sans[abs(no - str[i])].push_back(i);
        else
          sans[abs(no - str[i])].push_back(1000000 - i);
      }
      for (int i = 0; i < (10); ++i) sort(sans[i].begin(), sans[i].end());
      for (int i = 0; i < (10); ++i)
        for (int j = 0; j < (sans[i].size()); ++j) {
          if (K <= 0) break;
          K--;
          int cnt = sans[i][j];
          if (cnt > 500000) cnt -= 1000000;
          str[abs(cnt)] = no;
        }
      if (str < ansstr) ansstr = str;
    }
  cout << ansstr << endl;
}
