가장 가벼운 언어

알파벳 $A_k$ 는 영어 알파벳의 처음 $k$ 개 문자로 이루어진다. 각 문자에는 양의 정수 가중치가 하나씩 정해져 있다. $A_k$ 의 문자들로 만든 단어의 가중치는 그 단어에 들어 있는 모든 문자의 가중치를 더한 값이고, 언어($A_k$ 위의 단어들로 이루어진 임의의 유한 집합)의 가중치는 그 언어에 속한 모든 단어의 가중치를 더한 값이다.

어떤 언어에서 한 단어가 다른 단어의 접두사가 되는 경우가 전혀 없으면, 그 언어를 접두사 없는(prefixless) 언어라고 부른다. 정확히 $n$ 개의 단어로 이루어진 접두사 없는 언어의 가중치가 가질 수 있는 최솟값을 구하는 것이 목표다.

예를 들어 $k = 2$ 이고 $W(a) = 2$, $W(b) = 5$ 라고 하자. 그러면 $W(ab) = 2 + 5 = 7$ 이고 $W(aba) = 2 + 5 + 2 = 9$ 이다. 언어 $\{ab, aba, b\}$ 는 $ab$ 가 $aba$ 의 접두사이므로 접두사 없는 언어가 아니다. $A_2$ 위에서 단어가 3 개인 가장 가벼운 접두사 없는 언어는 $\{b, aa, ab\}$ 이고, 그 가중치는 $5 + 4 + 7 = 16$ 이다.

$n$, $k$ 와 $k$ 개 문자의 가중치가 주어질 때, $A_k$ 위에서 정확히 $n$ 개의 단어로 이루어진 접두사 없는 언어의 최소 가중치를 계산하라.

첫째 줄에 두 정수 $n$ 과 $k$ 가 공백 하나로 구분되어 주어진다 ($2 \le n \le 10\,000$, $2 \le k \le 26$). 각각 언어에 들어가는 단어의 개수와 알파벳의 문자 개수이다.

둘째 줄에는 $k$ 개의 양의 정수가 공백 하나로 구분되어 주어지며, 각 값은 $10\,000$ 이하이다. $i$ 번째 수는 $i$ 번째 문자의 가중치이다.

$A_k$ 위에서 정확히 $n$ 개의 단어로 이루어진 접두사 없는 언어의 최소 가중치를 정수 하나로 출력한다.