2021. [NOI 2015]荷马史诗

【题目描述】

一部《荷马史诗》有$n$种不同的单词，从$1$到$n$编号。

其中第$i$种单词出现的总次数为$w_i$。Allison想用$k$进制串$s_i$来替换第$i$种单词，

使得任意$1\leq i,j\leq n,i\neq j$都有，$s_i$不是$s_j$的前缀

举个栗子：

A:"abcdirutyiuertyiryt"

B:"abcdir"

则B是A的前缀

$k$进制字符串：每个字符是$0$到$k-1$之间的整数。

一个字符串被称为$k$进制字符串，当且仅当它的每个字符是$0$到$k−1$之间(包括$0$和$k−1$)的整数。

字符串$str1$被称为字符串$str2$的前缀，当且仅当：存在$1\leq t\leq m$，使得$str1 = str2[1\ldots t]$。其中，$m$是字符串$str2$的长度，$str2[1\ldots t]$ 表示$str2$的前$t$个字符组成的字符串。

【输入格式】

第一行两个正整数$n,k$，表示$n$个单词使用$k$进制字符串替换。

接下来$n$行，第$i+1$行包含1个非负整数$w_i$，表示第$i$中单词的出现次数。

【输出格式】

第一行为《荷马史诗》经过编码后的最短长度。

第二行为保证最短总长度的情况下，最长字符串$s_i$的最短长度。

【样例输入1】

4 2
1
1
2
2

【样例输出1】

12
2

【样例输入2】

6 3
1
1
3
3
9
9

【样例输出2】

36
3

【数据范围与提示】

对于40%的数据$k=2$；

对于45%的数据$n\leq 1,000$；

对于100%的数据,$k\leq 9，n\leq 10^5$。

选手请注意用64位整数

对于每个测试点：

若第一行正确，得到40%的分数；

若完全正确，得到100%的分数。

【来源】

NOI 2015 Day 2 T1