题目描述

一个$n$位十进制数字(0-9)组成的数字字符串是一个完美数串当且仅当这个数字字符串中有至少$K$位数字相同。例如$n=4, K = 2$，数串1223,1111, 2233都是完美数串，而1234不是完美数串。

可以将数串中的一个数字修改为其他任意的数字，修改的代价是修改前和修改后的数字的绝对值。例如，可以把”1234“修改为”1134, 2234, 1233, 1244等，修改的代价都是1，并且修改后都是完美数串。

给定长度为$n$的数字字符串和$K$，求将该字符串修改为完美数串的最小代价以及在最小代价下的字典序最小的完美数串。

题目输入

第一行包含两个整数$n$和$K$，第二行是一个包含$n$个数字字符的字符串。每个字符都是'0' -- '9'。

题目输出

第一行是一个整数，表示最小的修改代价。

第二行是在最小修改代价下得到的字典序最小的完美数串。

样例输入1

4 2
1234

样例输出1

1
1134

样例输入2

6 5
787585

样例输出2

4
777577

范围说明

• 对于30%的数据有：$2leq K leq n leq 10$；
• 另有30%的数据有：$2leq K leq n leq 1000$；
• 剩下40%的数据有：$2leq K leq n leq 10^5$。