#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> nums(n);
  vector<int> numfreq(10);
  for (int i = 0; i < n; i++) {
    char a;
    cin >> a;
    nums[i] = a - '0';
    numfreq[nums[i]]++;
  }
  int best = 10000000;
  string beststring = "";
  for (int i = 0; i < 10; i++) {
    int kd = k;
    vector<int> dist(10);
    int cost = 0;
    for (int j = 0; j < 10; j++) {
      int cur = 0;
      if (i + j < 10) cur += numfreq[j + i];
      if (j != 0 && i - j >= 0) cur += numfreq[i - j];
      cost += j * min(kd, cur);
      dist[j] += min(kd, cur);
      kd -= min(kd, cur);
    }
    if (cost <= best) {
      string ans = "";
      for (int j = 0; j < n; j++) {
        int cur = nums[j];
        if (dist[abs(i - cur)] > 0 && i <= cur) {
          dist[abs(i - cur)]--;
          ans += (char)('0' + i);
        } else
          ans += (char)('0' + cur);
      }
      for (int j = n - 1; j >= 0; j--) {
        int cur = ans[j] - '0';
        if (dist[abs(i - cur)] > 0) {
          dist[abs(i - cur)]--;
          ans[j] = (char)('0' + i);
        } else
          ans[j] = (char)('0' + cur);
      }
      if (cost == best)
        beststring = min(beststring, ans);
      else {
        best = cost;
        beststring = ans;
      }
    }
  }
  cout << best << endl << beststring << endl;
  return 0;
}
