In Homeric Epics there are ~n~ different words numbered from ~1~ to ~n~. The ~i~-th word appears ~w_i~ times in the text. Allison wants to substitute the ~i~-th word with a ~k~-ary string ~s_i~, satisfying the following constraint: for any ~1 \le i,j \le n~, ~i \ne j~, ~s_i~ is not the prefix of ~s_j~.

Allison wants to know how to choose ~s_i~ so that the resulting text has minimum length. Under the assumption that the total length of the text is minimal, Allison wants to know what is the shortest possible length of the longest ~s_i~.

A string is called a ~k~-ary string if and only if its characters are in ~\{0, 1, \dots, k-1\}~.

A string ~s_1~ is said to be a prefix of ~s_2~ if and only if there exists ~1 \le t \le m~ such that ~s_1 = s_2[1 \dots t]~ where ~m~ is the length of ~s_2~ and ~s_2[1 \dots t]~ represents the substring of ~s_2~ formed by the first ~t~ characters.

Input Specification

The first line of the input file contains two integers ~n,k~ separated by one space, denoting there are ~n~ words in total and we need to substitute the words with a ~k~-ary string.

In the following ~n~ lines, the ~(i+1)~-th line has a nonnegative integer ~w_i~ denoting the number of times the ~i~-th word has occurred.

Output Specification

The output consists of two lines. The first line is an integer denoting the minimum length of the Homeric Epics after substitution. The second line is an integer denoting the minimum length of the longest string ~s_i~ given the total length is minimum.

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

Constraints

Test Case	~n~	~k~	Additional Constraints	~w_i~
1	~n=3~	~k=2~		~0 < w_i \le 10^{11}~
2	~n=5~	~k=2~
3	~n=16~	~k=2~	All ~w_i~ are equal.
4	~n=1000~	~k=2~	The ~w_i~ are generated uniformly at random.
5	~n=1000~	~k=2~
6	~n=100\,000~	~k=2~
7	~n=100\,000~	~k=2~	All ~w_i~ are equal.
8	~n=100\,000~	~k=2~
9	~n=7~	~k=3~
10	~n=16~	~k=3~	All ~w_i~ are equal.
11	~n=1001~	~k=3~	All ~w_i~ are equal.
12	~n=99\,999~	~k=4~	All ~w_i~ are equal.
13	~n=100\,000~	~k=4~
14	~n=100\,000~	~k=4~
15	~n=1000~	~k=5~
16	~n=100\,000~	~k=7~	The ~w_i~ are generated uniformly at random.
17	~n=100\,000~	~k=7~
18	~n=100\,000~	~k=8~	The ~w_i~ are generated uniformly at random.
19	~n=100\,000~	~k=9~
20	~n=100\,000~	~k=9~

Scoring

For each test case:

• If only the first line is correct, ~40\%~ of points will be awarded;
• If both lines are correct, ~100\%~ of points will be awarded.