#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  int n, t1;
  cin >> n >> t1 >> s;
  int dig[100001];
  for (int i = 0; i < n; i++) {
    dig[i] = s[i] - '0';
  }
  string ans = "";
  int res = 1 << 30;
  for (int j = 0; j < n; j++) {
    ans += 'z';
  }
  for (int i = 0; i < 10; i++) {
    int t = t1;
    int pre = 0;
    string cal = s;
    for (int j = 0; j < 10; j++) {
      if (i + j < 10) {
        for (int k = 0; k < n && t > 0; k++) {
          if (dig[k] == i + j) {
            cal[k] = i + '0';
            pre += j;
            t--;
          }
        }
      }
      if (i - j >= 0 && j != 0) {
        for (int k = n - 1; k >= 0 && t > 0; k--) {
          if (dig[k] == i - j) {
            cal[k] = i + '0';
            pre += j;
            t--;
          }
        }
      }
    }
    if (pre < res) {
      res = pre;
      ans = cal;
    } else if (pre == res) {
      if (ans > cal) {
        ans = cal;
        res = pre;
      }
    }
  }
  cout << res << endl << ans << endl;
  return 0;
}
