[NOI2015Day2-A]荷马史诗

内存限制：512 MB 时间限制：1000 ms

追逐影子的人，自己就是影子 ——荷马

Allison最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有$𝑛$种不同的单词，从1到𝑛进行编号。其中第$𝑖$种单词出现的总次数为$𝑤_𝑖$。Allison想要用$𝑘$进制串$𝑠_𝑖$来替换第$𝑖$种单词，使得其满足如下要求：

对于任意的$1≤𝑖,𝑗≤𝑛，𝑖 \ne 𝑗$，都有：$𝑠_𝑖$不是$𝑠_𝑗$的前缀。

现在Allison想要知道，如何选择$𝑠_𝑖$，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison还想知道最长的$𝑠_𝑖$的最短长度是多少?

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

字符串$𝑆𝑡𝑟_1$被称为字符串$𝑆𝑡𝑟_2$的前缀，当且仅当：存在$1 ≤ 𝑡 ≤ 𝑚$，使得$𝑆𝑡𝑟_1 = 𝑆𝑡𝑟_2[1..𝑡]$。其中，$𝑚$是字符串$𝑆𝑡𝑟_2$的长度，$𝑆𝑡𝑟_2[1..𝑡]$表示$𝑆𝑡𝑟_2$的前$𝑡$个字符组成的字符串。

第1行包含2个正整数$𝑛, 𝑘$，中间用单个空格隔开，表示共有$𝑛$种单词，需要使用$𝑘$进制字符串进行替换。接下来$𝑛$行，第$𝑖+1$行包含1个非负整数$𝑤_𝑖$，表示第$𝑖$种单词的出现次数。

第1行输出1个整数，为《荷马史诗》经过重新编码以后的最短长度。

第2行输出1个整数，为保证最短总长度的情况下，最长字符串$𝑠_𝑖$的最短长度。

12
2

36
3

【样例说明1】

用$𝑋(𝑘)$表示$𝑋$是以$𝑘$进制表示的字符串。

一种最优方案：令$00_{(2)}$替换第1种单词，$01_{(2)}$替换第2种单词，$10_{(2)}$替换第3种单词，$11_{(2)}$替换第4种单词。在这种方案下，编码以后的最短长度为：1 × 2 + 1 × 2 + 2 × 2 + 2 × 2 = 12

最长字符串$𝑠_𝑖$的长度为2。

一种非最优方案：令$000_{(2)}$替换第1种单词，$001_{(2)}$替换第2种单词，$01_{(2)}$替换第3种单词，$1_{(2)}$替换第4种单词。在这种方案下，编码以后的最短长度为：1×3+1×3+2×2+2×1 = 12

最长字符串$𝑠_𝑖$的长度为3。与最优方案相比，文章的长度相同，但是最长字符串的长度更长一些。

【样例说明2】

一种最优方案：令$000_{(3)}$替换第1种单词，$001_{(3)}$替换第2种单词，$01{(3)}$替换第3种单词，$02_{(3)}$替换第4种单词，$1_{(3)}$替换第5种单词，$2_{(3)}$替换第6种单词。

【数据规模与约定】

所有测试数据的范围和特点如下表所示

屏幕快照 2019-06-04 下午8.30.36.png

【提示】

选手请注意使用64位整数进行输入输出、存储和计算。

【评分方式】（comet 暂不支持部分分）

对于每个测试点：
若输出文件的第1行正确，得到该测试点40%的分数；
若输出文件完全正确，得到该测试点100%的分数。

C0394 [NOI2015Day2-A]荷马史诗