Номер машины в Берляндии состоит ровно из n цифр. Номер называется красивым, если в нем есть хотя бы k одинаковых цифр. Вася хочет поменять цифры в номере своей машины так, чтобы он стал красивым. За замену одной из n цифр номера нужно заплатить сумму денег, равную модулю разности старой и новой цифры.
Помогите Васе: найдите минимальную стоимость замены номера Васиной машины на красивый. Также требуется найти получившийся в итоге красивый номер. Если таких несколько, нужно вывести лексикографически наименьший.
Выходные данные
В первой строке выведите минимальное количество денег, которые потребуются Васе для замены номера. Во второй строке выведите новый номер машины. Если решений несколько, выведите лексикографически наименьшее.
Примечание
В первом примере замена второй цифры на «8» стоит |9 - 8| = 1. Замена пятой цифры на «8» стоит столько же. Замена шестой цифры стоит |6 - 8| = 2. В итоге Вася заплатит 1 + 1 + 2 = 4 чтобы получить красивый номер «888188».
Лексикографическое сравнение строк реализует оператор < в современных языках программирования. Строка x лексикографически меньше строки y, если существует такое i (1 ≤ i ≤ n), что xi < yi, а для любого j (1 ≤ j < i) xj = yj. Сравниваемые строки в этой задаче всегда имеют длину n.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 5
898196
|
4
888188
|
|
2
|
3 2
533
|
0
533
|
|
3
|
10 6
0001112223
|
3
0000002223
|