#include <bits/stdc++.h>
using namespace std;
static const double EPS = 1e-10;
template <typename T, typename S>
vector<T>& operator<<(vector<T>& a, S b) {
  a.push_back(b);
  return a;
}
template <typename T>
void operator>>(vector<T>& a, int b) {
  while (b--)
    if (!a.empty()) a.pop_back();
}
bool isprime(int n) {
  if (n < 2) return false;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
long long b_pow(long long x, long long n) {
  return n ? b_pow(x * x, n / 2) * (n % 2 ? x : 1) : 1ll;
}
string itos(int n) {
  stringstream ss;
  ss << n;
  return ss.str();
}
vector<int> pos[10];
int main() {
  ios_base::sync_with_stdio(false);
  string s;
  int n, m;
  cin >> n >> m;
  cin >> s;
  int e[10] = {0};
  for (int i = 0; (int)i < (int)s.size(); i++) {
    e[s[i] - '0']++;
    pos[s[i] - '0'].push_back(i);
  }
  string ans;
  vector<int> can;
  int mi = INT_MAX;
  pair<int, string> W = make_pair(INT_MAX, "~");
  for (int X = 0; X < 10; X++) {
    if (e[X] < m) {
      string mur = s;
      int sum = 0;
      int t = m - e[X];
      for (int i = 1; i <= 9; i++) {
        int x = X - i;
        int y = X + i;
        if (y <= 9) {
          int j = 0;
          while (j < pos[y].size() && t) {
            mur[pos[y][j]] = X + '0';
            sum += i;
            t--;
            j++;
          }
        }
        if (x >= 0) {
          int j = pos[x].size() - 1;
          while (j >= 0 && t) {
            mur[pos[x][j]] = X + '0';
            sum += i;
            t--;
            j--;
          }
        }
      }
      W = min(W, make_pair(sum, mur));
    } else if (e[X] >= m) {
      cout << 0 << endl;
      cout << s << endl;
      return 0;
    }
  }
  cout << W.first << endl;
  cout << W.second << endl;
}
