#P18805. [POI1998] 最轻的前缀语言
[POI1998] 最轻的前缀语言
[POI1998] 最轻的前缀语言
题目描述
有一个由前 个小写英文字母组成的字母表,每个字母都有一个正整数权值。一个字符串的权值是其中所有字母权值的总和。
一个语言是一个由不同字符串组成的有限集合。语言的权值是其中所有字符串权值的总和。
如果语言中的任意一个字符串都不是另一个字符串的前缀,则称这个语言是前缀无关的。
请构造一个恰好包含 个不同非空字符串的前缀无关语言,使语言的权值最小。你只需要输出这个最小权值,不需要输出字符串本身。
例如,字母 a、b 的权值分别是 、 时,集合 {b, aa, ab} 前缀无关,权值为 ;它是包含三个字符串的最轻前缀无关语言。
输入格式
第一行两个整数 ,,。
第二行 个正整数,第 个数表示第 个字母的权值。每个权值都不超过 。
输出格式
输出一个整数,表示符合要求的语言的最小权值。
样例输入
3 2
2 5
样例输出
16