用c++解决下述问题：描述 有些词有力量。它可以使包含它的字符串变得更强大（更大的重量）。字符串中单词的权重定义为其在字符串中的出现次数乘以其值，而字符串的权重定义为所有单词权重的总和。给定一些单词及其值，您应该输出由这些单词组成的字符串，这些单词使字符串的权重最大。输入 输入由多个测试用例组成。输入的第一行是整数 T，表示测试用例的数量。每个测试用例都以一行开头，该行由两个整数组成：N 和 M，指示字符串的最大长度和单词数。以下 M 行中的每一行都包含一个单词 Wi。每个测试用例的最后一行由 M 个整数组成，而第 i 个数字表示 Wi 的值 Vi。技术规格： 1. T ≤ 15 2.0 < N ≤ 50， 0 < M ≤ 100。3.每个单词的长度小于11，大于0。4. 1 ≤ Vi ≤ 100.5.输入中的所有单词都不同。6. 所有单词都由“a”-“z”组成。输出 对于每个测试用例，输出在一行中具有最大权重的字符串。如果有多个答案，则输出最短的答案。如果仍有多个答案，则按字典顺序输出最小的答案。答案可能是一个空字符串。

下面是该问题的 C++ 代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 105;
const int MAXL = 15;
const int MAXLEN = 55;
const int MAXW = 26;

int T, N, M, w[MAXW], dp[MAXN][MAXLEN];
char s[MAXN][MAXLEN];

int main() {
    cin >> T;
    while (T--) {
        cin >> N >> M;
        for (int i = 1; i <= M; i++) {
            cin >> s[i] >> w[i];
        }
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        for (int i = 1; i <= M; i++) {
            for (int j = N; j >= 0; j--) {
                for (int k = strlen(s[i]); k <= j; k++) {
                    if (dp[j-k][0] != -1) {
                        int val = dp[j-k][0] + w[i];
                        if (dp[j][0] < val || (dp[j][0] == val && strcmp(s[i], s[dp[j][1]]) < 0)) {
                            dp[j][0] = val;
                            dp[j][1] = i;
                        }
                    }
                }
            }
        }
        cout << s[dp[N][1]];
        for (int i = 1; i < N - strlen(s[dp[N][1]]) + 1; i++) {
            cout << " " << s[dp[N][1]];
        }
        cout << endl;
    }
    return 0;
}

该算法的基本思路是动态规划。首先，对于一个长度为 $j$ 的字符串，我们需要求出由给定单词组成的字符串，使得其权值最大。设 $dp[j]$ 表示长度为 $j$ 的字符串的最大权值，$dp[j][0]$ 表示最大权值，$dp[j][1]$ 表示使用的最后一个单词的编号。初始时，$dp[0][0]$ 为 0。

接下来，我们按照单词的顺序，依次考虑每个单词。对于第 $i$ 个单词，我们需要考虑它是否能够被加入到字符串中。因此，我们需要枚举当前字符串长度 $j$，并在其中寻找一个位置 $k$，使得该单词可以被加入到字符串中。具体地，我们需要满足 $k \geqslant |W_i|$，且 $dp[j-k]$ 不为 -1（即 $j-k$ 这个长度的字符串可以由给定单词组成）。如果满足这两个条件，我们可以尝试将该单词加入到字符串中，计算新的权值 $val = dp[j-k][0] + w[i]$，并与 $dp[j][0]$ 进行比较。如果 $val$ 更大，或者 $val$ 相等但单词 $W_i$ 的字典序更小，我们就更新 $dp[j][0]$ 和 $dp[j][1]$。

最终，我们可以输出长度为 $N$ 的字符串的最大权值，即 $dp[N][0]$ 对应的单词 $W_{dp[N][1]}$，并将它输出 $N/|W_{dp[N][1]}|$ 次，即可得到最终的答案。