#include <bits/stdc++.h>
using namespace std;
struct node {
  string a;
  int cost;
} ans[1005];
int sum[10];
bool cmp(node a, node b) {
  if (a.cost == b.cost) return a.a < b.a;
  return a.cost < b.cost;
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  char str[10005], arr[10005];
  scanf("%s", str);
  int f = 0;
  for (int i = 0; i < n; i++) {
    sum[str[i] - '0']++;
    if (sum[str[i] - '0'] >= k) {
      f = 1;
      break;
    }
  }
  if (f)
    puts("0"), printf("%s\n", str);
  else {
    int pos = 0;
    for (int i = 0; i <= 9; i++) {
      strcpy(arr, str);
      int sum1 = 0;
      int need = k - sum[i];
      int cost = 0;
      for (int j = 1; j <= 9; j++) {
        for (int k = 0; k < n; k++) {
          if (arr[k] - '0' == i + j) {
            sum1++;
            arr[k] = i + '0';
            cost += j;
          }
          if (sum1 >= need) break;
        }
        if (sum1 >= need) break;
        for (int k = n - 1; k >= 0; k--) {
          if (arr[k] - '0' == i - j) {
            sum1++;
            arr[k] = i + '0';
            cost += j;
          }
          if (sum1 >= need) break;
        }
      }
      ans[pos].a.assign(arr);
      ans[pos].cost = cost;
      pos++;
    }
    sort(ans, ans + pos, cmp);
    printf("%d\n", ans[0].cost);
    cout << ans[0].a << endl;
  }
  return 0;
}
