题目描述

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\)。