OI题库

字母表AK由英文字母表的大写字母K组成。一个被称作重量的正整数被委派给字母表的每一个字母。一个由字母表AK的字母组成的字符串的重量是这个字 符串的所有字母的总重量。一个基于字母表AK的语言由这个字母表的字母组成的字符串的有限集合。一个语言的重量是所有它的字符串的重量之和。如果这个语言 的任意两个字符串W、V，W不是V的前缀，那我们说这个语言不是前缀的。

我们想找出基于字母表AK的N个要素的非前缀语言的可能的最小重量。

例如

假设K=2，字母a的重量W（a）=2 字母b的重量W（b）=5。字符串ab的重量W（ab）=2+5=7。 W（aba）=2+5+2=9。语言J={ab，aba，b}的重量-W（J）=21。语言J不是非前缀，因为字符串ab是aba的前缀。基于字母表A2最轻的三元非前缀语言（假设字母的重量如前）是{b，aa，ab}；它的重量是16。

任务

写一个程序：

• 从文本文件中读取两个整数n，k和字母表Ak 的k个字母的重量；
• 计算基于字母表Ak 的非前缀的n元语言的最小重量；
• 把结果写到文本文件。

输入

在输入文件的首行有两个被空格号分开的正整数n、k(2<=n<=10000, 2<=k<=26)。它们是语言中的字符串数和字母表中各个字母数。第二行包括被空格号隔开的k个正整数。每一个都不大于10000。第I个数是第I个字母的重量。

输出

在输出文件的首行应该写一个整数-基于字母表Ak 的最轻的非前缀的n元语言重量。

样例输入  

3 2
2 5

样例输出  

16