#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### 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 *F _{i}*.

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 *L _{i}*. 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

*L*multiplied by

_{i}*F*. Rar the Cat wants the shortest possible encoded string by asking you to minimize this sum.

_{i}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 *i ^{th}* line describes

*F*.

_{i}### 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 *i ^{th}* line should be

*L*, the length of the encoded string you have assigned for character

_{i}*i*.

### Limits

For all testcases, 0 ≤ *F _{i}* ≤ 10

^{12}. 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.### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 20 | 9 | 1s | 256MB | Minimum |

2 | 35 | 11 | 1s | 256MB | Minimum |

3 | 45 | 22 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o huffman -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512