题目描述

Oiers国的汽车号牌恰好由 $n$ 位数字($0 \sim 9$)组成。一个漂亮的汽车号牌必须是号牌中至少要出现 $k$ 个相同数字(是哪个数字无所谓)。Smart也想把他现在的汽车号牌变得漂亮，而每修改号牌中的$1$ 位数字必须支付一定的金额，该金额等于旧数字和新数字之间差的绝对值。

Smart需要你的帮忙，他想知道他至少应该支付多少金额才能使自己的汽车号牌变得漂亮，你还应该告诉他修改后最终的漂亮号牌，如果有几个这样的号牌满足所付金额最少，则输出字典序最小的那一个。

格式

输入格式

第一行包含两个整数 $n$ 和 $k$ ，分别表示汽车号牌有 $n$ 位数字以及漂亮号牌中应有 $k$ 个相同的数字。

第二行由 $n$ 位数字组成，它描述了Smart汽车的旧号牌。该数字不包含空格，仅包含数字($0 \sim 9$)。

输出格式

第一行输出Smart更改号牌需要支付的最小金额。

第二行输出汽车的新号牌，如果有多个方案，请输出字典序最小的方案。

样例1

样例输入1

4 1
1234

样例输出1

0
1234

限制

$20\%$的数据：$1≤ k ≤ n ≤25$；

$50\%$的数据：$1≤ k ≤ n ≤1000$；

$100\%$的数据：$2 ≤ k ≤ n ≤ 10^4$。