#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, k, ans, mn = 1e9;
char s[10010];
pair<int, int> cost[N], t[N];
int res[N], id, idx, ID;
string str[11];
string tmp;
int main(int argc, char **argv) {
  scanf("%d%d%s", &n, &k, s);
  for (int j = 0; j < n; ++j) s[j] -= '0';
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < n; ++j) {
      cost[j].first = abs(s[j] - i);
      cost[j].second = j;
    }
    sort(cost, cost + n);
    ans = 0;
    for (int j = 0; j < k; ++j) ans += cost[j].first;
    if (ans < mn) {
      id = 0;
      res[id++] = i;
      mn = ans;
    } else if (ans == mn)
      res[id++] = i;
  }
  for (int i = 0; i < id; ++i) {
    for (int j = 0; j < n; ++j) {
      cost[j].first = abs(s[j] - res[i]);
      cost[j].second = j;
    }
    sort(cost, cost + n);
    tmp = "";
    for (int j = 0; j < n; ++j) tmp += char(s[j] + '0');
    int mx = -1;
    for (int j = 0; j < k; ++j) mx = max(cost[j].first, mx);
    int K = 0;
    ID = 0;
    for (int j = 0; j < k; ++j)
      if (cost[j].first != mx) {
        ++K;
        tmp[cost[j].second] = res[i] + '0';
      }
    for (int j = 0; j < n; ++j) {
      if (cost[j].first != mx) continue;
      if (res[i] < s[cost[j].second])
        t[ID++] = make_pair(res[i] - s[cost[j].second], cost[j].second);
      else
        t[ID++] = make_pair(res[i] - s[cost[j].second], -cost[j].second);
    }
    sort(t, t + ID);
    for (int j = 0; j < k - K; ++j) tmp[abs(t[j].second)] = res[i] + '0';
    str[idx++] = tmp;
  }
  sort(str, str + idx);
  cout << mn << endl;
  cout << str[0] << endl;
  return 0;
}
