题目描述

大多数人都尝试过在手机的数字键盘上输入短信。在输入较长的消息时，这有时会非常烦人，因为通常需要多次按同一个键才能输入一个字母。这是由于键盘上的按键数量较少。典型的手机只有12个按键（可能还有一些不用于输入的控制键）。此外，只有8个按键用于输入英语的26个字母。字母在键盘上的标准分配如左图所示：

1      2abc   3def     1       2abcd   3efg     
4ghi   5jkl   6mno     4hijk   5lm     6nopq
7pqrs  8tuv   9wxyz    7rs     8tuv    9wxyz
*      0space #        *      0space   #

每个按键分配了3或4个字母。如果你想输入某个组的第一个字母，只需按该键一次；如果想输入第二个字母，则需要按该键两次；其他字母则需要按该键三次或四次。键盘的设计者并未尝试优化按键布局以减少按键次数，而是倾向于将字母均匀分配到各个按键上。然而，某些字母比其他字母更常用。一些高频字母被分配到了按键的第三甚至第四位置。例如，字母$S$在英语中非常常见，但我们需要按四次键才能输入它。如果字母的分配方式如右图所示，键盘对于输入普通英语文本会更加方便。

ACM决定在其新款手机上采用一个优化后的键盘布局。现在他们需要一个计算机程序，能够根据给定的字母频率找到最优的键盘布局。我们需要保持字母的字母顺序，因为如果字母顺序混乱，用户会感到困惑。但我们可以将任意数量的字母分配到同一个按键上。

输入格式

第一行输入一个正整数$T$，表示测试用例的数量。每个测试用例的第一行包含两个整数$K$和$L$（$1 \leq K \leq L \leq 90$），分别表示按键的数量和需要映射到这些按键上的字母数量。接下来是两行：第一行包含$K$个字符，每个字符代表一个按键的名称；第二行包含$L$个字符，代表字母表中的字母。按键和字母由数字、字母（区分大小写）或任何标点符号（ASCII码在33到126之间）表示。没有两个按键的名称相同，也没有两个字母相同。然而，字母的名称也可以用作按键的名称。

接下来的$L$行，每行包含一个正整数$F_1, F_2, \ldots, F_L$，表示每个字母的频率，按顺序从第一个字母开始。数字越大表示该字母越常见。频率不会超过100000。

输出格式

为每个测试用例找到一个最优的键盘布局。最优键盘是指输入平均文本时“价格”最低的键盘。价格由每个字母的价格之和决定。字母的价格是其频率（$F_i$）与其在按键上的位置的乘积。字母的顺序不能改变，必须按照给定的顺序分组。

如果存在多个价格相同的解，我们尝试最大化最后一个按键上的字母数量，然后是倒数第二个按键，依此类推。

更正式地说，你需要找到一个序列$P_1, P_2, \ldots, P_L$，表示每个字母在特定按键上的位置。该序列必须满足以下条件：

1. $P_1 = 1$
2. 对于每个$i > 1$，要么$P_i = P_{i-1} + 1$，要么$P_i = 1$
3. 最多有$K$个$P_i$满足$P_i = 1$
4. 乘积和$SP = F_1 \times P_1 + F_2 \times P_2 + \ldots + F_L \times P_L$最小
5. 对于任何其他满足这些条件且和$SQ = SP$的序列$Q$，存在一个$M$（$1 \leq M \leq L$），使得对于任何$J$（$M < J \leq L$），$P_J = Q_J$，且$P_M > Q_M$

每个测试用例的输出必须以一行Keypad #I:开头，其中$I$是测试用例的序号，从1开始。接下来是$K$行，每行代表一个按键，顺序与输入中的按键顺序相同。每行包含按键的字符、冒号、一个空格以及分配给该按键的字母列表。字母之间不分开。

每个测试用例之后输出一个空行，包括最后一个测试用例。

示例输入

1
8 26
23456789
ABCDEFGHIJKLMNOPQRSTUVWXYZ
3371
589
1575
1614
6212
971
773
1904
2989
123
209
1588
1513
2996
3269
1080
121
2726
3083
4368
1334
518
752
427
733
871

示例输出

Keypad #1:
2: ABCD
3: EFG
4: HIJK
5: LM
6: NOPQ
7: RS
8: TUV
9: WXYZ

来源

Central Europe 2000