NOI 2015: 荷马史诗 (Huffman tree)

NOI2015 Day2荷马史诗问题解析

问题描述

追逐影子的人，其本身亦为影子。 ——荷马

Allison 最近对文学产生了浓厚兴趣。她喜欢在慵懒的午后，细细品味一杯卡布奇诺，安静地阅读她钟爱的《荷马史诗》。然而，《荷马史诗》由《奥德赛》与《伊利亚特》组成，篇幅过于庞大，Allison 希望借助一种编码方式将其缩短。
《荷马史诗》中包含了 n 种不同的单词，编号从 1 到 n。其中第 i 种单词出现的总次数为 wi。Allison 想要使用 k 进制字符串 si 来替代第 i 种单词，并满足以下条件：
对于任意的 1≤i,j≤n，且 i≠j，si 都不能成为 sj 的前缀。
现在 Allison 想知道如何选择 si 才能使替换后的《荷马史诗》长度最小。在保证总长度最短的前提下，她还希望了解最长的 si 可能达到的最短长度是多少？
所谓 k 进制字符串是指每个字符均为整数且范围介于 0 到 k−1（包含两端）。
若字符串 Str1 是字符串 Str2 的前缀，则意味着存在某个 t（1≤t≤m），使得 Str1 等同于 Str2 的前 t 个字符组成的子串。

输入格式

输入文件的第一行包含两个正整数 n 和 k，中间以空格分隔，表示共有 n 种单词，