Background

Those who chase shadows are themselves shadows — Homer

Problem Description

Allison has recently become fascinated with literature. She enjoys spending lazy afternoons sipping a cup of cappuccino and quietly reading her beloved "The Iliad and Odyssey." However, the epic composed of "The Odyssey" and "The Iliad" is too long for Allison, who wants to use a coding method to make it shorter.

In "The Iliad and Odyssey," there are \( n \) different words, numbered from \( 1 \) to \( n \). The total occurrences of the \( i \)-th word are \( w_i \). Allison wants to replace the \( i \)-th word with a \( k \)-ary string \( s_i \) that satisfies the following requirements:

For any \( 1 \leq i, j \leq n \) with \( i \neq j \), \( s_i \) is not a prefix of \( s_j \).

Allison wants to know how to choose \( s_i \) to minimize the length of the new "The Iliad and Odyssey" after replacement. Additionally, she wants to know the shortest possible length of the longest \( s_i \) under the condition of minimizing the total length.

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

A string \( str1 \) is called a prefix of string \( str2 \) if there exists \( 1 \leq t \leq m \) such that \( str1 = str2[1..t] \). Here, \( m \) is the length of \( str2 \), and \( str2[1..t] \) represents the first \( t \) characters of \( str2 \).

Input Format

The first line of input contains two positive integers \( n \) and \( k \), separated by a single space, indicating there are \( n \) different words and a \( k \)-ary string is needed for replacement.

The next \( n \) lines contain one non-negative integer each, \( w_i \), indicating the occurrences of the \( i \)-th word.

Output Format

The output includes two lines.

The first line contains one integer, the shortest length of "The Iliad and Odyssey" after re-encoding.

The second line contains one integer, the shortest length of the longest string \( s_i \) under the condition of minimizing the total length.

Sample Input and Output

Sample Input #1

4 2
1
1
2
2

Sample Output #1

12
2

Sample Input #2

6 3
1
1
3
3
9
9

Sample Output #2

36
3

Notes

Sample 1 Explanation

An optimal solution: Use \( 00(2) \) to replace the 1st word, \( 01(2) \) to replace the 2nd word, \( 10(2) \) to replace the 3rd word, and \( 11(2) \) to replace the 4th word. The shortest length after encoding is:

\( 1 \times 2 + 1 \times 2 + 2 \times 2 + 2 \times 2 = 12 \)

The length of the longest \( s_i \) is \( 2 \).

A non-optimal solution: Use \( 000(2) \) to replace the 1st word, \( 001(2) \) to replace the 2nd word, \( 01(2) \) to replace the 3rd word, and \( 1(2) \) to replace the 4th word. The shortest length after encoding is:

\( 1 \times 3 + 1 \times 3 + 2 \times 2 + 2 \times 1 = 12 \)

The length of the longest \( s_i \) is \( 3 \). Compared to the optimal solution, the article's length is the same, but the longest string's length is longer.

Sample 2 Explanation

An optimal solution: Use \( 000(3) \) to replace the 1st word, \( 001(3) \) to replace the 2nd word, \( 01(3) \) to replace the 3rd word, \( 02(3) \) to replace the 4th word, \( 1(3) \) to replace the 5th word, and \( 2(3) \) to replace the 6th word.

Data Range and Constraints

All test data are within the following ranges (all \( w_i \) satisfy \( 0 < w_i \leq 10^{11} \)):

Hints

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

Scoring Method

For each test case:

• If the first line of the output file is correct, 40% of the points for that test case are awarded.
• If the entire output file is correct, 100% of the points for that test case are awarded.

见题面 Input 部分

见题面 Output 部分