用c++解决下述问题：描述 Some words have power. It can make a string containing it become more powerful (larger weight). The weight of a word in a string is defined as the number of its occurences in the string multiplied by its value, while the weight of the string is defined as the sum of all words' weights. Given some words with their values, you should output the string consisting of these words which make the string's weight maximal. 输入 The input consists of multiple test cases. The first line of the input is an integer T, indicating the number of the test cases. Each test case starts with a line consisting of two integers: N and M, indicating the string's maximum length and the number of the words. Each of the following M lines consists of a word Wi. The last line of each test case consists of M integers, while the i-th number indicates the value Vi of Wi. Technical Specification: 1. T ≤ 15 2. 0 < N ≤ 50, 0 < M ≤ 100. 3. The length of each word is less than 11 and bigger than 0. 4. 1 ≤ Vi ≤ 100. 5. All the words in the input are different. 6. All the words just consist of 'a' - 'z'. 输出 For each test case, output the string which has the maximal weight in a single line.If there are multiple answers, output the shortest one. If there are still multiple answers, output the smallest one in lexicographical order. The answer may be an empty string.

这道题需要使用动态规划来解决。我们可以定义dp[i]表示长度为i的字符串的最大权值，它可以通过枚举最后一个单词得到。具体地，我们枚举最后一个单词为Wi，那么dp[i]就可以由dp[i-len(Wi)] + Vi得到，其中len(Wi)表示单词Wi的长度，Vi表示单词Wi的权值。最后我们在dp数组中找到最大权值的位置，然后倒推出字符串即可。

代码如下：