#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  int ans = 2e9;
  vector<int> can;
  vector<string> cand;
  for (int i = 0; i < 10; i++) {
    priority_queue<int> pq;
    int t = 0;
    for (int j = 0; j < s.length(); j++) {
      int alpha = s[j] - '0';
      int cost = abs(alpha - i);
      pq.push(-cost);
    }
    for (int j = 0; j < k; j++) {
      int cst = -pq.top();
      pq.pop();
      t += cst;
    }
    if (ans > t) {
      can.clear();
      can.push_back(i);
      ans = t;
    } else if (ans == t) {
      can.push_back(i);
    }
  }
  for (int d = 0; d < can.size(); d++) {
    string temp = s;
    int num = can[d];
    int need = k;
    vector<pair<int, int> > big;
    vector<pair<int, int> > small;
    vector<pair<int, int> > ord;
    int cnt[10];
    memset(cnt, 0, sizeof(cnt));
    priority_queue<int> pq;
    for (int j = 0; j < s.size(); j++) {
      int cst = abs(num - (s[j] - '0'));
      if (cst) pq.push(-cst);
      if (s[j] - '0' == num) need--;
      if (s[j] - '0' > num) big.push_back({s[j] - '0', j});
      if (s[j] - '0' < num) small.push_back({s[j] - '0', j});
    }
    reverse(small.begin(), small.end());
    for (int i = 0; i < big.size(); i++) {
      int cost = abs(big[i].first - num);
      ord.push_back({cost, big[i].second});
    }
    for (int i = 0; i < small.size(); i++) {
      int cost = abs(small[i].first - num);
      ord.push_back({cost, small[i].second});
    }
    if (need <= 0) {
      cout << 0 << endl << s;
      exit(0);
    }
    for (int i = 0; i < need; i++) {
      int cst = -pq.top();
      pq.pop();
      cnt[cst]++;
    }
    for (int i = 0; i < ord.size(); i++) {
      int cst = ord[i].first;
      int idx = ord[i].second;
      if (cnt[cst]) {
        cnt[cst]--;
        temp[idx] = (char)(num + '0');
      }
    }
    cand.push_back(temp);
  }
  cout << ans << "\n";
  sort(cand.begin(), cand.end());
  cout << cand[0];
  return 0;
}
