故事背景

Loony 教授是我的一位挚友，他怒气冲冲地闯进我的办公室，满脸通红。他开口的第一句话就是：“该死的手机制造商！我刚才想发条短信，结果光是输入一行字就花了我十多分钟。” 我试图让他冷静下来。“怎么了？为什么会花这么长时间？” 他继续说道：“你没看出来吗？！他们对字母的布局简直是一团糟！为什么 's' 是它所在按键上的第 4 个字母？还有 'e'？为什么它不是按键上的第一个字母？为了输入一个 's'，我竟然要按 4 次 '7'？这简直是疯了！”

“冷静点，我的朋友，” 我说，“这种方案已经沿用很久了，甚至在短信发明之前就存在了。他们不得不保持这种布局。”

“那不是借口，” 他的脸变得越来越红，“是时候改变这一切了。从一开始这就是个愚蠢的主意。既然我们要改，为什么他们只在 8 个按键上放字母？为什么不把 12 个按键都用上？而且为什么它们必须是连续的？”

“嗯……我……不知道，” 我回答道。

“好了，就这样。那些人显然是不称职的。我相信一定有人能想出更好的方案。”

我看得出来，他就是那种只会抱怨问题却从不尝试去解决它的人。

在本题中，你需要设计一种最优的按键字母布局，以最小化输入一条消息所需的按键次数。给定按键的数量、每个按键最多能放置的字母数量、字母表中的字母总数，以及每种字母在消息中出现的频率。字母可以放置在任何按键的任何位置，且顺序不限。每个字母只能出现在一个按键上。此外，字母表中的字母数量可能超过 26 个（它不是英语）。

作为参考，目前的手机键盘布局如下：

key 2: abc
key 3: def
key 4: ghi
key 5: jkl
key 6: mno
key 7: pqrs
key 8: tuv
key 9: wxyz

第一次按下按键会输入该按键上的第一个字母。随后每按一次，都会切换到下一个字母。例如，要输入单词 "snow"，你需要按 4 次 "7"，接着按 2 次 "6"，再按 3 次 "6"，最后按 1 次 "9"。总按键次数为 10。

输入格式

输入文件的第一行包含测试用例的数量 $N$。接下来是 $N$ 个测试用例。每个用例包含两行。第一行包含每个按键最多能放置的字母数量 $P$、可用按键的数量 $K$ 以及字母表中的字母数量 $L$，均由空格分隔。第二行包含 $L$ 个非负整数。每个数字代表相应字母的频率。第一个数字表示第一个字母的使用次数，第二个数字表示第二个字母的使用次数，依此类推。

输出格式

对于每个用例，你应该输出以下内容：

Case #x: [minimum number of keypad presses]

其中包含为最优布局输入消息所需的按键次数。

数据范围

时间限制：1 秒。

内存限制：1GB。

$P \times K \ge L$

$0 \le$ 每个字母的频率 $\le 1000000$

小数据（测试集 1 - 可见；5 分）

$1 \le N \le 10$

$1 \le P \le 10$

$1 \le K \le 12$

$1 \le L \le 100$

大数据（测试集 2 - 隐藏；10 分）

$1 \le N \le 100$

$1 \le P \le 1000$

$1 \le K \le 1000$

$1 \le L \le 1000$

样例

样例输入 1

2
3 2 6
8 2 5 2 4 9
3 9 26
1 1 1 100 100 1 1 1 1 1 1 1 1 1 1 1 1 10 11 11 11 11 1 1 1 100

样例输出 1

Case #1: 47
Case #2: 397