2132: 最优前缀编码
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
因为某种原因，小Y最近常将自己写的信编码来防止别人偷看。
所谓编码，即给信息内所有的字符以唯一的“编码”，来代替原字符传输或存储。 为了保证信息能够被正确的还原，小Y规定，编码必须符合一定的规则。
假设小Y的信息基于字符集α，要用K个字符来为其编码，定义它的前缀编码S为一个集合，它包含了N个不同字符串，与字符集中的元素一一对应，并满足以下两个条件：
1.每一个字符串仅包含字符 '0','1', ...。
2.对于集合中任意两个字符串x和y，x不是y的前缀。 当一个编码为前缀编码时，它所表示的内容能够被快速唯一地还原，常见的等长编码即为前缀编码。
假定字符集α中的每个元素出现概率相等，那么前缀编码S的代价可以被定义为字符集中所有元素编码字符的代价之和。 因为小Y要写很多信，而他写每个字符需要的代价都是不一样的（比划数或者其他不同）。为了方便，他需要知道如何为字符集编码，才能做到代价最小。
输入
输入第一行包含两个整数N,K,分别表示字符集大小，编码字符个数。 第二行包含K个正整数，即K个字符各自的代价。
输出
输出仅一行，包含一个整数minCost，表示前缀编码的最小代价。
样例输入 复制
3 2
1 4样例输出 复制
11提示
样例1说明：
最优的前缀编码为{"00","01","1"}。
输入样例2：
3 3
1 3 5
输出样例2：
9
样例2说明：
有两种前缀编码代价最小：{"0","1","2"}，{"00","01","1"}。
输入样例3：
500 10
1 2 3 4 5 6 7 8 9 10
输出样例3：
4732
数据规模：
对于30%的数据 N <= 10，K <= 5。
对于50%的数据 K <= 10。
对于100%的数据 N <= 500，K <= 50，每个字符的代价小于等于100。