#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  char str[n + 1];
  scanf("%s", str);
  int count[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  int check[n];
  for (int i = 0; i < n; ++i) {
    check[i] = str[i] - '0';
    count[check[i]]++;
  }
  int s_min[10], min_i;
  for (int i = 0; i < 10; ++i) {
    s_min[i] = 0;
  }
  int str_min[10][n];
  for (int i = 0; i < 10; ++i) {
    int del[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int cnt = count[i];
    int a = i - 1, b = i + 1;
    while (cnt < k) {
      if (b < 10) {
        if (cnt + count[b] <= k) {
          cnt += count[b];
          s_min[i] += count[b] * abs(b - i);
          del[b] = count[b];
        } else {
          del[b] = k - cnt;
          s_min[i] += (k - cnt) * abs(b - i);
          cnt = k;
        }
        b++;
      }
      if (a >= 0) {
        if (cnt + count[a] <= k) {
          cnt += count[a];
          del[a] = count[a];
          s_min[i] += abs(a - i) * count[a];
        } else {
          del[a] = k - cnt;
          s_min[i] += abs(a - i) * (k - cnt);
          cnt = k;
        }
        a--;
      }
    }
    int count_s[10];
    for (int j = 0; j < 10; ++j) {
      count_s[j] = count[j];
    }
    for (int j = 0; j < n; ++j) {
      if (del[check[j]]) {
        if (del[check[j]] < count_s[check[j]] && check[j] < i) {
          str_min[i][j] = check[j];
          count_s[check[j]]--;
        } else {
          str_min[i][j] = i;
          count_s[check[j]]--;
          del[check[j]]--;
        }
      } else {
        str_min[i][j] = check[j];
      }
    }
    if (!i) {
      min_i = s_min[i];
    } else {
      min_i = min(min_i, s_min[i]);
    }
  }
  int finish[n];
  bool yes = false;
  for (int i = 0; i < 10; ++i) {
    if (s_min[i] == min_i) {
      if (!yes) {
        for (int j = 0; j < n; ++j) {
          finish[j] = str_min[i][j];
        }
        yes = true;
      } else {
        for (int j = 0; j < n; ++j) {
          if (finish[j] != str_min[i][j]) {
            if (str_min[i][j] < finish[j]) {
              for (int k = 0; k < n; ++k) {
                finish[k] = str_min[i][k];
              }
            } else {
              break;
            }
          }
        }
      }
    }
  }
  printf("%d\n", min_i);
  for (int i = 0; i < n; ++i) {
    printf("%d", finish[i]);
  }
  return 0;
}
