Problem Description
While Rar the Cat is teaching huffman encoding, he wondered if its possible to use Huffman Encoding on non-binary strings.
After some Googling, Rar the Cat found that it is actually possible. Hence, he wants you to implement Huffman Encoding for strings where each encoded digit is between 0 and K-1.
Rar the Cat's string has N characters, each with frequency Fi.
To perform Huffman Encoding, you are to assign a K-ary string to each of the N characters. Assume character i is assigned to a K-ary string with length Li. To encode the string, Rar the Cat will replace every character i in the string with the K-ary string that is assigned. Hence, the total length of the encoded message would be the sum of Li multiplied by Fi. Rar the Cat wants the shortest possible encoded string by asking you to minimize this sum.
In addition, to ensure that the message can be decoded properly, each encoded string must be unique. In addition, no encoded string can be a prefix of another encoded string.
For example, there cannot be a set of assigned binary strings {0, 1, 01} as '0' is a prefix of '01'. However, the set {0, 10, 11} is valid.
Input
The first line of input contains 2 integers N and K.
N lines of integers follow, the ith line describes Fi.
Output
You are to output a single integer on the first line, the minimum length of the encoded string.
Subsequently, you are to output N lines containing 1 integer each. On the ith line should be Li, the length of the encoded string you have assigned for character i.
Limits
For all testcases, 0 ≤ Fi ≤ 1012. However, it is guaranteed that the answer will fit into a 64-bit signed integer.
Subtask 1 (20%): 1 ≤ N ≤ 100000, K = 2.
Subtask 2 (35%): 1 ≤ N ≤ 2000. 2 ≤ K ≤ 9.
Subtask 3 (45%): 1 ≤ N ≤ 100000. 2 ≤ K ≤ 9.
Subtask 4 (0%): Sample Testcases.
Sample Testcase 1
Input
4 2
1
1
2
2
Output
12
2
2
2
2
Explanation
The encoded string of abccdd is 00 01 10 10 11 11.
Sample Testcase 2
Input
4 3
1
1
2
2
Output
8
2
2
1
1
Explanation
The encoded string of abccdd is 00 01 1 1 2 2.
Sample Testcase 3
Input
3 2
1
2
3
Output
9
2
2
1
Explanation
The encoded string of abbccc is 00 01 01 1 1 1.