题面翻译

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的最轻的3元素的，无前缀的语言（假定字母的重量依据前面所给的）是{b,aa,ab}，它的重量是16。

输入格式

第一行有两个正整数n和k，它们由空格分开，2≤n≤10000，2≤k≤26，它们各自代表语言中单词的数目和字母表中的字母的数目。

第二行包含k个由空格分开的正整数。它们都不超过10000，第i个数是第i个字母的重量。

输出格式

唯一一行有一个整数——关于Ak字母表的n元素的无前缀的语言的最轻的重量。

样例 #1

样例输入 #1

3 2
2 5

样例输出 #1

16