#include <bits/stdc++.h>
using namespace std;
int N, K;
char C[10010], Now[10010], Fin[10010];
int tim[20], size, fincost = 1 << 30;
int main() {
  cin >> N >> K >> C;
  for (; C[size] != '\0'; ++size) ++tim[C[size] - '0'];
  for (int i = 9; i >= 0; --i) {
    int need = K - tim[i], cost = 0;
    memcpy(Now, C, sizeof(Now));
    for (int dif = 1; dif <= 9 && need > 0; ++dif) {
      for (int j = 0; j < size && need > 0; ++j)
        if (C[j] == i + '0' + dif) {
          --need;
          cost += dif;
          Now[j] = i + '0';
        }
      for (int j = size - 1; j >= 0 && need > 0; --j)
        if (C[j] == i + '0' - dif) {
          --need;
          cost += dif;
          Now[j] = i + '0';
        }
    }
    if (cost < fincost) {
      fincost = cost;
      memcpy(Fin, Now, sizeof(Fin));
    } else if (cost == fincost)
      if (memcmp(Now, Fin, sizeof(Now)) < 0) memcpy(Fin, Now, sizeof(Fin));
  }
  cout << fincost << '\n' << Fin;
}
