Khi nghiên cứu và triển khai một mô hình AI lên các thiết bị IoT, sau quá trình huấn luyện, nhóm sinh viên thu được một mô hình biểu diễn bởi một chuỗi ~s~ gồm ~n~ trọng số. Nhằm tối ưu cho phần cứng, các trọng số đã được lượng tử hóa thành các số nguyên từ ~0~ đến ~9~. Để giảm dung lượng lưu trữ, họ cần biến đổi mô hình sao cho có ít nhất ~k~ trọng số mang cùng một giá trị. Có thể chọn thay đổi một trọng số đang có giá trị ~x~ thành một giá trị ~y~ thỏa mãn ~0 \le y \le 9~, thay đổi này sẽ làm suy giảm độ chính xác của mô hình một lượng bằng ~|x-y|~.

Yêu cầu: Tìm tổng độ suy giảm chính xác tối thiểu để mô hình có ít nhất ~k~ trọng số giống nhau và chuỗi trọng số thỏa mãn độ suy giảm chính xác tối thiểu. Nếu có nhiều cách thỏa mãn độ suy giảm chính xác tối thiểu, hãy in ra chuỗi trọng số có thứ tự từ điển nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên ~n, k~ lần lượt là số lượng trọng số của mô hình và số lượng trọng số tối thiểu cần phải giống nhau ~(2 \le k \le n \le 10^4)~.

• Dòng thứ hai chứa một chuỗi ~s~ gồm ~n~ chữ số lần lượt là các trọng số của mô hình.

Output

• Dòng đầu in ra một số nguyên là tổng độ suy giảm chính xác tối thiểu để tối ưu mô hình.

• Dòng thứ hai in ra chuỗi ~n~ trọng số mới của mô hình.

Scoring

Sample Input 1

6 5
898196

Sample Output 1

4
888188

Sample Input 2

10 6
0001112223

Sample Output 2

3
0000002223

Notes

Trong ví dụ thứ nhất, thay đổi giá trị tại vị trí ~2, 5, 6~. Tổng độ suy giảm chính xác tối thiểu là: ~1+1+2=4~.

Trong ví dụ thứ hai, thay đổi giá trị tại vị trí ~4, 5, 6~. Tổng độ suy giảm chính xác tối thiểu là: ~1+1+1=3~.