"He who chases shadows is a shadow himself." — Homer

Allison has recently become fascinated by literature. On a lazy afternoon, she enjoys sipping a cappuccino and quietly reading her favorite book, The Homeric Epics. However, this monumental work, consisting of The Odyssey and The Iliad, is simply too long. Allison wants to use an encoding scheme to make it shorter.

A Homeric Epic contains $n$ different words, numbered from $1$ to $n$. The total frequency of the $i$-th word is $w_i$. Allison wants to replace the $i$-th word with a $k$-ary string $s_i$ such that the following requirement is met:

For any $1 \le i, j \le n, i \neq j$, $s_i$ is not a prefix of $s_j$.

Now, Allison wants to know how to choose $s_i$ to minimize the total length of the new Homeric Epic. While ensuring the total length is minimized, Allison also wants to know the minimum possible length of the longest string $s_i$.

A string is called a $k$-ary string if and only if each of its characters is an integer between $0$ and $k-1$ (inclusive).

A string $S_1$ is called a prefix of a string $S_2$ if and only if there exists $1 \le t \le m$ such that $S_1 = S_2[1..t]$, where $m$ is the length of $S_2$, and $S_2[1..t]$ represents the string consisting of the first $t$ characters of $S_2$.

Input

Read data from the file epic.in.

The first line of the input file contains two positive integers $n$ and $k$, separated by a single space, indicating that there are $n$ types of words that need to be replaced using $k$-ary strings.

The next $n$ lines each contain a non-negative integer $w_i$, representing the frequency of the $i$-th word.

Output

Output to the file epic.out.

The output file contains 2 lines.

The first line outputs one integer, the minimum total length of the Homeric Epic after re-encoding.

The second line outputs one integer, the minimum length of the longest string $s_i$ while ensuring the total length is minimized.

Examples

Input 1

4 2
1
1
2
2

Output 1

12
2

Note 1

Let $X_{(k)}$ denote that $X$ is a string represented in base $k$.

One optimal scheme: Let $00_{(2)}$ replace the 1st word, $01_{(2)}$ replace the 2nd word, $10_{(2)}$ replace the 3rd word, and $11_{(2)}$ replace the 4th word. In this scheme, the minimum length after encoding is: $1 \times 2 + 1 \times 2 + 2 \times 2 + 2 \times 2 = 12$ The length of the longest string $s_i$ is $2$.

One non-optimal scheme: Let $000_{(2)}$ replace the 1st word, $001_{(2)}$ replace the 2nd word, $01_{(2)}$ replace the 3rd word, and $1_{(2)}$ replace the 4th word. In this scheme, the minimum length after encoding is: $1 \times 3 + 1 \times 3 + 2 \times 2 + 2 \times 1 = 12$ The length of the longest string $s_i$ is $3$. Compared to the optimal scheme, the length of the text is the same, but the length of the longest string is longer.

Input 2

6 3
1
1
3
3
9
9

Output 2

36
3

Note 2

One optimal scheme: Let $000_{(3)}$ replace the 1st word, $001_{(3)}$ replace the 2nd word, $01_{(3)}$ replace the 3rd word, $02_{(3)}$ replace the 4th word, $1_{(3)}$ replace the 5th word, and $2_{(3)}$ replace the 6th word.

Input 3

See epic/epic.in and epic/epic.ans in the contestant directory.

Constraints

The range and characteristics of all test data are shown in the table below:

Note

Contestants should be aware to use 64-bit integers for input, output, storage, and calculations.

Subtasks

For each test case: If the first line of the output file is correct, you will receive 40% of the points for that test case; If the output file is completely correct, you will receive 100% of the points for that test case.