#include <bits/stdc++.h>
using namespace std;
int A[11];
string tmpa;
int f(int dig, int i, int k) {
  if (k == 0) return (0);
  int newk = k;
  if (dig + i <= 9) {
    newk = max(0, newk - A[dig + i]);
    for (int ii = 0, kk = 0; ii < tmpa.length(), kk < k - newk; ii++)
      if (tmpa[ii] == dig + i + '0') {
        tmpa[ii] = dig + '0';
        kk++;
      }
  }
  int buf = newk;
  if (dig - i >= 0) {
    newk = max(0, newk - A[dig - i]);
    for (int ii = tmpa.length() - 1, kk = 0; ii >= 0, kk < buf - newk; ii--)
      if (tmpa[ii] == dig - i + '0') {
        tmpa[ii] = dig + '0';
        kk++;
      }
  }
  int res = (k - newk) * i;
  return (res + f(dig, i + 1, newk));
}
int main() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  for (int i = 0; i < s.length(); i++) {
    A[s[i] - '0']++;
  }
  int res = INT_MAX;
  string ans;
  for (int i = 0; i < 10; i++) {
    tmpa = s;
    int tmp = f(i, 1, max(0, k - A[i]));
    if (res == tmp) {
      ans = min(ans, tmpa);
      continue;
    }
    if (res > tmp) {
      res = tmp;
      ans = tmpa;
    }
  }
  cout << res << endl;
  cout << ans;
exit:
  return (0);
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

A car number in Berland consists of exactly n digits. A number is called beautiful if it has at least k equal digits. Vasya wants to change the digits in his car's number so that the number became beautiful. To replace one of n digits Vasya has to pay the sum of money, equal to the absolute difference between the old digit and the new one.

Help Vasya: find the minimum sum of money he should pay to make the number of his car beautiful. You should also find the resulting beautiful number. If there are several such numbers, then print the lexicographically minimum one.

Input

The first line contains two space-separated integers n and k (2 ≤ n ≤ 104, 2 ≤ k ≤ n) which represent how many digits the number has and how many equal digits a beautiful number should have. The second line consists of n digits. It describes the old number of Vasya's car. It is guaranteed that the number contains no spaces and only contains digits.

Output

On the first line print the minimum sum of money Vasya needs to change the number. On the second line print the car's new number. If there are several solutions, print the lexicographically minimum one.

Examples

Input

6 5
898196


Output

4
888188


Input

3 2
533


Output

0
533


Input

10 6
0001112223


Output

3
0000002223

Note

In the first sample replacing the second digit with an "8" costs |9 - 8| = 1. Replacing the fifth digit with an "8" costs the same. Replacing the sixth digit costs |6 - 8| = 2. As a result, Vasya will pay 1 + 1 + 2 = 4 for a beautiful number "888188".

The lexicographical comparison of strings is performed by the < operator in modern programming languages. The string x is lexicographically smaller than the string y, if there exists such i (1 ≤ i ≤ n), that xi < yi, and for any j (1 ≤ j < i) xj = yj. The strings compared in this problem will always have the length n.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int A[11];
string tmpa;
int f(int dig, int i, int k) {
  if (k == 0) return (0);
  int newk = k;
  if (dig + i <= 9) {
    newk = max(0, newk - A[dig + i]);
    for (int ii = 0, kk = 0; ii < tmpa.length(), kk < k - newk; ii++)
      if (tmpa[ii] == dig + i + '0') {
        tmpa[ii] = dig + '0';
        kk++;
      }
  }
  int buf = newk;
  if (dig - i >= 0) {
    newk = max(0, newk - A[dig - i]);
    for (int ii = tmpa.length() - 1, kk = 0; ii >= 0, kk < buf - newk; ii--)
      if (tmpa[ii] == dig - i + '0') {
        tmpa[ii] = dig + '0';
        kk++;
      }
  }
  int res = (k - newk) * i;
  return (res + f(dig, i + 1, newk));
}
int main() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  for (int i = 0; i < s.length(); i++) {
    A[s[i] - '0']++;
  }
  int res = INT_MAX;
  string ans;
  for (int i = 0; i < 10; i++) {
    tmpa = s;
    int tmp = f(i, 1, max(0, k - A[i]));
    if (res == tmp) {
      ans = min(ans, tmpa);
      continue;
    }
    if (res > tmp) {
      res = tmp;
      ans = tmpa;
    }
  }
  cout << res << endl;
  cout << ans;
exit:
  return (0);
}

```