#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 6;
const long long M = 1e9 + 7;
const long long inf = 1e18;
int main() {
  int n;
  scanf("%d", &n);
  int k;
  scanf("%d", &k);
  string s, res;
  cin >> s;
  string ans = s, answer = s;
  int fre[10] = {0};
  for (int i = 0; i < n; i++) {
    int d = s[i] - 48;
    fre[d]++;
  }
  int req[10] = {0}, dist;
  for (int i = 0; i < 10; i++) {
    int res = 0, ct = fre[i];
    for (dist = 1; dist < 10; dist++) {
      if (ct >= k) break;
      int low = i - dist, high = i + dist;
      if (low >= 0) {
        if (ct + fre[low] >= k) {
          int need = k - ct;
          int money = dist * need;
          res += money;
          ct = k;
          break;
        } else {
          int money = dist * fre[low];
          res += money;
          ct += fre[low];
        }
      }
      if (high < 10) {
        if (ct + fre[high] >= k) {
          int need = k - ct;
          int money = dist * need;
          res += money;
          ct = k;
          break;
        } else {
          int money = dist * fre[high];
          res += money;
          ct += fre[high];
        }
      }
    }
    req[i] = res;
  }
  int mn = 1e9, pos = -1;
  for (int i = 0; i < 10; i++) {
    if (mn > req[i]) {
      mn = req[i];
      pos = i;
    }
  }
  for (int ch = 0; ch < 10; ch++) {
    if (req[ch] != mn) continue;
    int ct = fre[ch];
    pos = ch;
    ans = s;
    for (dist = 1; dist < 10; dist++) {
      if (ct >= k) break;
      int low = pos - dist, high = pos + dist;
      if (high < 10) {
        if (ct + fre[high] >= k) {
          int need = k - ct;
          ct = k;
          for (int i = 0; i < n && need; i++) {
            if (ans[i] - 48 == high) {
              ans[i] = (char)(pos + 48);
              need--;
            }
          }
          break;
        } else {
          ct += fre[high];
          int need = fre[high];
          for (int i = 0; i < n && need; i++) {
            if (ans[i] - 48 == high) {
              ans[i] = (char)(pos + 48);
              need--;
            }
          }
        }
      }
      if (low >= 0) {
        if (ct + fre[low] >= k) {
          int need = k - ct;
          ct = k;
          for (int i = n - 1; i >= 0 && need; i--) {
            if (ans[i] - 48 == low) {
              ans[i] = (char)(pos + 48);
              need--;
            }
          }
          break;
        } else {
          ct += fre[low];
          int need = fre[low];
          for (int i = 0; i < n && need; i++) {
            if (ans[i] - 48 == low) {
              ans[i] = (char)(pos + 48);
              need--;
            }
          }
        }
      }
    }
    if (answer == s)
      answer = ans;
    else if (answer > ans)
      answer = ans;
  }
  cout << mn << "\n";
  cout << answer;
  cout << "\n";
}
