Homeric Epics

Homeric Epics에는 $1$부터 $n$까지 번호가 붙은 서로 다른 단어 $n$개가 있습니다. $i$번째 단어는 본문에 $w\_i$번 나타납니다. Allison은 $i$번째 단어를 $k$진 문자열 $s\_i$로 바꾸려 합니다. 이때 모든 $1 \le i,j \le n$ ($i \ne j$)에 대해 $s\_i$는 $s\_j$의 접두사가 될 수 없습니다.

Allison은 본문의 전체 길이가 최소가 되도록 $s\_i$를 어떻게 고를 수 있는지 알고 싶어 합니다. 또한 전체 길이가 최소인 경우에 가장 긴 $s\_i$의 길이가 가질 수 있는 최솟값도 알고 싶어 합니다.

문자열의 모든 문자가 $\{0, 1, \dots, k-1\}$에 속하면 그 문자열을 $k$진 문자열이라고 합니다.

문자열 $s\_1$이 $s\_2$의 접두사라는 것은, $1 \le t \le m$인 어떤 $t$에 대해 $s\_1 = s\_2\[1 \dots t]$가 성립하는 것을 말합니다. 여기서 $m$은 $s\_2$의 길이이고, $s\_2\[1 \dots t]$는 $s\_2$의 앞 $t$개 문자로 이루어진 부분 문자열입니다.

입력 파일의 첫 줄에는 공백으로 구분된 두 정수 $n$, $k$가 주어집니다. 이는 단어가 총 $n$개이고, 이들을 $k$진 문자열로 바꿔야 함을 뜻합니다.

이어지는 $n$개의 줄 중 $(i+1)$번째 줄에는 $i$번째 단어가 등장한 횟수를 나타내는 음이 아닌 정수 $w\_i$가 주어집니다.

출력은 두 줄입니다. 첫 줄에는 치환 후 Homeric Epics의 전체 길이의 최솟값을 정수로 출력합니다. 둘째 줄에는 전체 길이가 최소인 경우에서 가장 긴 $s\_i$의 길이의 최솟값을 정수로 출력합니다.

• $3 \le n \le 100\,000$
• $2 \le k \le 9$
• $0 < w\_i \le 10^{11}$