The Lightest Language

The alphabet $A_k$ consists of the first $k$ letters of the English alphabet. Each letter is assigned a positive integer weight. The weight of a word built from letters of $A_k$ is the sum of the weights of all its letters, and the weight of a language (any finite set of words over $A_k$) is the sum of the weights of all its words.

A language is called prefixless if no word in it is a prefix of another word in it. The goal is to find the smallest possible weight of a prefixless language that has exactly $n$ words.

For example, let $k = 2$ with $W(a) = 2$ and $W(b) = 5$. Then $W(ab) = 2 + 5 = 7$ and $W(aba) = 2 + 5 + 2 = 9$. The language $\{ab, aba, b\}$ is not prefixless, because $ab$ is a prefix of $aba$. The lightest prefixless language with three words over $A_2$ is $\{b, aa, ab\}$, and its weight is $5 + 4 + 7 = 16$.

Given $n$, $k$, and the weights of the $k$ letters, compute the minimum weight of a prefixless language of exactly $n$ words over $A_k$.

The first line contains two integers $n$ and $k$ separated by a single space ($2 \le n \le 10\,000$, $2 \le k \le 26$): the number of words in the language and the number of letters in the alphabet, respectively.

The second line contains $k$ positive integers separated by single spaces, each at most $10\,000$. The $i$-th of them is the weight of the $i$-th letter.

Print a single integer: the minimum weight of a prefixless language of exactly $n$ words over the alphabet $A_k$.