#include <bits/stdc++.h>
using namespace std;
int cnt[11] = {0};
int n, k;
string s;
void in() {
  cin >> n >> k;
  cin >> s;
  for (int i = 0; i <= n - 1; i++) {
    cnt[s[i] - '0']++;
  }
}
void solve() {
  string tmp[11];
  int vals[11];
  int ans = 10 * n;
  int ctr;
  int cost;
  int a;
  for (int i = 0; i <= 9; i++) {
    ctr = k - cnt[i];
    tmp[i] = s;
    cost = 0;
    for (int diff = 1; diff <= 10 && ctr > 0; diff++) {
      a = i + diff;
      if (a <= 9) {
        for (int p = 0; p < n; p++) {
          if (ctr > 0 && tmp[i][p] == (a + '0')) {
            tmp[i][p] = '0' + i;
            cost += diff;
            ctr--;
          }
        }
      }
      a = i - diff;
      if (a >= 0) {
        for (int p = n - 1; p >= 0; p--) {
          if (ctr > 0 && tmp[i][p] == (a + '0')) {
            tmp[i][p] = '0' + i;
            cost += diff;
            ctr--;
          }
        }
      }
    }
    vals[i] = cost;
  }
  for (int i = 0; i <= 9; i++) {
    if (vals[i] < ans) {
      ans = vals[i];
      s = tmp[i];
    } else if (vals[i] == ans) {
      if (tmp[i] < s) s = tmp[i];
    }
  }
  cout << ans << endl << s << endl;
}
int main() {
  in();
  solve();
  return 0;
}
