#include <bits/stdc++.h>
using namespace std;
int rasp, n, k, x, sum, v[10], i, j, legit[10], schimb[10][10], mi;
char c, s[10001], s2[10][10001];
int main() {
  cin >> n >> k;
  cin >> s;
  for (i = 0; i < n; i++) {
    c = s[i];
    v[c - '0']++;
  }
  rasp = 1000000;
  for (i = 0; i <= 9; i++) {
    x = k - v[i];
    if (x <= 0) {
      cout << 0 << '\n';
      for (i = 0; i < n; i++) {
        cout << s[i];
      }
      return 0;
    } else {
      j = 1;
      sum = 0;
      while (i + j <= 9 && i - j >= 0) {
        sum += j * min(v[i + j], x);
        schimb[i][i + j] += min(v[i + j], x);
        x -= min(v[i + j], x);
        if (x == 0) {
          rasp = min(rasp, sum);
          break;
        }
        sum += j * min(v[i - j], x);
        schimb[i][i - j] += min(v[i - j], x);
        x -= min(v[i - j], x);
        if (x == 0) {
          rasp = min(rasp, sum);
        }
        j++;
      }
      while (i + j <= 9) {
        sum += j * min(v[i + j], x);
        schimb[i][i + j] += min(v[i + j], x);
        x -= min(v[i + j], x);
        if (x == 0) {
          rasp = min(rasp, sum);
          break;
        }
        j++;
      }
      while (i - j <= 9) {
        sum += j * min(v[i - j], x);
        schimb[i][i - j] += min(v[i - j], x);
        x -= min(v[i - j], x);
        if (x == 0) {
          rasp = min(rasp, sum);
          break;
        }
        j++;
      }
    }
    legit[i] = sum;
  }
  cout << rasp << '\n';
  if (rasp == 0) {
    for (i = 0; i <= n; i++) {
      cout << s[i];
    }
    return 0;
  }
  for (i = 0; i <= 9; i++) {
    if (legit[i] == rasp) {
      for (j = 0; j < n; j++) {
        x = s[j] - '0';
        if (x < i) {
          continue;
        }
        if (schimb[i][x] >= 1) {
          schimb[i][x]--;
          s2[i][j] = i + '0';
        } else {
          s2[i][j] = x + '0';
        }
      }
      for (j = n - 1; j >= 0; j--) {
        x = s[j] - '0';
        if (x >= i) {
          continue;
        }
        if (schimb[i][x] >= 1) {
          schimb[i][x]--;
          s2[i][j] = i + '0';
        } else {
          s2[i][j] = x + '0';
        }
      }
    }
  }
  for (i = 0; i <= 9; i++) {
    if (legit[i] == rasp) {
      mi = i;
      break;
    }
  }
  for (i = mi + 1; i <= 9; i++) {
    if (legit[i] == rasp) {
      for (j = 0; j < n; j++) {
        if (s2[mi][j] > s2[i][j]) {
          mi = i;
          break;
        } else if (s2[mi][j] < s2[i][j]) {
          break;
        }
      }
    }
  }
  for (i = 0; i < n; i++) {
    cout << s2[mi][i];
  }
  return 0;
}
