K-ary Huffman Encoding Optimization

Allison loves literature and is especially fond of Homer's epics. However, the two works The Odyssey and The Iliad are extremely long. She decides to shorten the epic by replacing each word with a code. There are n different words numbered from 1 to n and the i-th word appears w_i times. Allison wants to assign each word a $k$-ary string $s_i$, such that for any two different words $i$ and $j$, $s_i$ is not a prefix of $s_j$.

The goal is to choose the codes $s_i$ so that the total length of the encoded text, i.e. $$\sum_{i=1}^n w_i \cdot |s_i|,$$ is minimized. Under the condition that the total length is minimized, Allison also wishes to know the smallest possible value of the length of the longest code among all optimal assignments.

A string is called a $k$-ary string if every character is a digit between 0 and $k-1$ (inclusive). A string $A$ is a prefix of string $B$ if there exists an integer $t$ ($1 \le t \le |B|$) such that $A = B[1..t]$.

This problem is essentially about constructing an optimal prefix code (a generalization of Huffman coding to a $k$-ary tree). Note that in the case of a $k$-ary Huffman tree, if $(n-1)$ is not divisible by $(k-1)$, one must add a few dummy nodes (with frequency 0) so that a full $k$-ary tree is formed.

inputFormat

The first line contains two integers n and k ($1 \le n \le 10^5$, $2 \le k \le 10^5$), where n is the number of different words and k is the base of the code. The second line contains n integers $w_1, w_2, \dots, w_n$ ($0 \le w_i \le 10^9$), where $w_i$ represents the frequency of the i-th word. (When n = 1, output the answer as described below.)

outputFormat

Output two integers separated by a space. The first integer is the minimized total length of the encoded text, i.e. $$\sum_{i=1}^n w_i \cdot |s_i|,$$ and the second integer is the minimum possible value of the maximum codeword length among all optimal prefix codes.

sample

1 2
10

10 1