#104198. [BZOJ 4198] [Noi2015]荷马史诗

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

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

对于任意的 ,，都有： 不是 的前缀。

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

一个字符串被称为 进制字符串，当且仅当它的每个字符是 到 之间（包括 和 ）的整数。

字符串 被称为字符串 的前缀，当且仅当：存在 ，使得 。其中， 是字符串 的长度， 表示 的前 个字符组成的字符串。

输入文件的第 行包含 个正整数 ，中间用单个空格隔开，表示共有 种单词，需要使用 进制字符串进行替换。

接下来 行，第 行包含 个非负整数 ，表示第 种单词的出现次数。

输出文件包括 行。

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

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

样例输入 #1

4 2
1
1
2
2

样例输出 #1

12
2

用 表示 是以 进制表示的字符串。

一种最优方案：令 替换第 种单词， 替换第 种单词， 替换第 种单词， 替换第 种单词。在这种方案下，编码以后的最短长度为：

最长字符串 的长度为 。

一种非最优方案：令 替换第 种单词， 替换第 种单词， 替换第 种单词， 替换第 种单词。在这种方案下，编码以后的最短长度为：

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

对于所有数据，保证 , 。

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