#include <bits/stdc++.h>
using namespace std;
int N, K;
char S[10001], tmp[10001], res[10001];
int C[10];
int f(int v) {
  if (C[v] >= K) return 0;
  int c = 0;
  int r = K - C[v];
  for (int d = 1; d < 10 && r; d++) {
    int t = 0;
    if (v >= d) t += C[v - d];
    if (v + d < 10) t += C[v + d];
    c += d * min(r, t);
    r -= min(r, t);
  }
  return c;
}
int main(int argc, char** argv) {
  std::ios::sync_with_stdio(false);
  cin >> N >> K;
  cin >> S;
  for (int i = 0; i < N; i++) C[S[i] - '0']++;
  int mn = 1e9;
  vector<int> ans;
  for (int v = 0; v < 10; v++) {
    int t = f(v);
    if (mn > t) {
      mn = t;
      ans.clear();
      ans.push_back(v);
    } else if (mn == t) {
      ans.push_back(v);
    }
  }
  cout << mn << endl;
  tmp[N] = res[N] = 0;
  for (int i = 0; i < N; i++) res[i] = '9';
  for (int v : ans) {
    strcpy(tmp, S);
    int r = max(0, K - C[v]);
    for (int d = 1; d < 10 && r; d++) {
      for (int i = 0; i < N && r; i++) {
        int a = tmp[i] - '0';
        if (a - v == d) {
          tmp[i] = '0' + v;
          r--;
        }
      }
      for (int i = N - 1; i >= 0 && r; i--) {
        int a = tmp[i] - '0';
        if (v - a == d) {
          tmp[i] = '0' + v;
          r--;
        }
      }
    }
    if (strcmp(tmp, res) < 0) strcpy(res, tmp);
  }
  cout << res << endl;
  return 0;
}
