题目描述

Alphabet A $_{k}$ consists of k initial letters of English alphabet. A positive integer called a weight is assigned to each letter of the alphabet. A weight of a word built from the letters of the alphabet A $_{k}$ is the sum of weights of all letters in this word. A language over an alphabet A $_{k}$ is any finite set of words built from the letters of this alphabet. A weight of a language is the sum of weights of all its words. We say that the language is prefixless if for each pair of different words w, v from this language w is not a prefix of v.

We want to find out what is the minimal possible weight of an n-element, prefixless language over an alphabet A $_{k}$ .

输入格式

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.

In the first line of a test case there are two positive integers n and k separated by a single space, (2 <= n <= 10000, 2 <= k <= 26). These are the number of words in a language and the number of letters in an alphabet respectively. The second line contains k positive integers separated by single spaces. Each of them is not greater than 10000. The i-th number is the weight of the i-th letter.

输出格式

For each test case you should output one line with the weight of the lightest prefixless n-element language over the alphabet A $_{k}$ .

题目翻译

你需要在字符集大小为 k 的所有字符串中选择 n 个字符串出来，满足没有任何一个字符串是另一个字符串的前缀，且使得权值之和最小。一个字符串的权值为其中所有字符的权值之和（重复计算）。每个字母的权值事先给定。 输出这个最小值。

1
3 2
2 5

16