#include <bits/stdc++.h>
using namespace std;
int n, k, d;
int original[10005];
int digits[10005];
int best[10005];
int count_beautiful(int digit) {
  int count = 0;
  for (int i = 0; i < n; i++)
    if (digits[i] == digit) count++;
  return count;
}
bool cheaper(int i, int j) {
  if (original[i] == d) return false;
  if (original[j] == d) return true;
  if (abs(original[i] - d) != abs(original[j] - d))
    return abs(original[i] - d) < abs(original[j] - d);
  if (original[i] < d && original[j] < d) return i > j;
  if (original[i] > d && original[j] > d) return i < j;
  if (original[i] < d && original[j] > d) return false;
  if (original[i] > d && original[j] < d) return true;
  assert(false);
}
int find_cost(int digit) {
  vector<int> indices;
  for (int i = 0; i < n; i++) indices.push_back(i);
  d = digit;
  sort(indices.begin(), indices.end(), cheaper);
  memcpy(digits, original, sizeof(digits));
  int count = count_beautiful(digit);
  int cost = 0;
  for (int i = 0; i + count < k; i++) {
    int index = indices[i];
    assert(digits[index] != d);
    cost += abs(digits[index] - d);
    digits[index] = d;
  }
  return cost;
}
bool lexicographic(int *a, int *b) {
  int i;
  for (i = 0; i < n; i++)
    if (a[i] != b[i]) break;
  if (i == n) return true;
  return a[i] <= b[i];
}
int main() {
  scanf("%d %d", &n, &k);
  scanf(" ");
  for (int i = 0; i < n; i++) {
    char c;
    scanf("%c", &c);
    original[i] = c - '0';
  }
  int min_cost = INT_MAX;
  for (int i = 0; i <= 9; i++) {
    int cost = find_cost(i);
    if (cost < min_cost || (cost == min_cost && lexicographic(digits, best))) {
      min_cost = cost;
      memcpy(best, digits, sizeof(best));
    }
  }
  printf("%d\n", min_cost);
  for (int i = 0; i < n; i++) printf("%d", best[i]);
  printf("\n");
  return 0;
}
