#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k;
  cin >> n >> k;
  string str;
  cin >> str;
  vector<int> counts(10, 0);
  for (int i = 0; i < n; ++i) counts[str[i] - '0']++;
  int min_cost = 99999999;
  vector<int> best_digit;
  vector<int> best_gap;
  for (int i = 0; i < 10; ++i) {
    int cost = 0;
    int count_cur = counts[i];
    int gap = 1;
    while (count_cur < k) {
      int avail = i - gap >= 0 ? counts[i - gap] : 0;
      avail += i + gap < 10 ? counts[i + gap] : 0;
      int needed = min(avail, k - count_cur);
      cost += needed * gap;
      count_cur += needed;
      gap++;
    }
    if (count_cur >= k && cost <= min_cost) {
      if (cost < min_cost) {
        best_digit.clear();
        best_gap.clear();
      }
      min_cost = min(min_cost, cost);
      best_digit.push_back(i);
      best_gap.push_back(gap - 1);
    }
  }
  cout << min_cost << endl;
  string ans = string(1, 'z');
  for (int kk = 0; kk < best_digit.size(); ++kk) {
    string str2 = str;
    int needed = max(0, k - counts[best_digit[kk]]);
    for (int i = 0; i < str2.size(); ++i) {
      if (needed > 0 && abs(str2[i] - '0' - best_digit[kk]) < best_gap[kk] &&
          str2[i] != char(best_digit[kk] + '0')) {
        str2[i] = best_digit[kk] + '0';
        needed--;
      }
    }
    for (int i = 0; i < str2.size(); ++i) {
      if (needed > 0 && str2[i] == char(best_digit[kk] + '0' + best_gap[kk])) {
        str2[i] = best_digit[kk] + '0';
        needed--;
      }
    }
    for (int i = str2.size() - 1; i >= 0; --i) {
      if (needed > 0 && str2[i] == char(best_digit[kk] + '0' - best_gap[kk])) {
        str2[i] = best_digit[kk] + '0';
        needed--;
      }
    }
    ans = min(ans, str2);
  }
  cout << ans << endl;
  return 0;
}
