代码测试（3）
http://bit.ly/aaAR1p
The story
Professor Loony, a dear friend of mine, stormed into my office. His face was red and he looked very angry. The first thing that came out of his mouth was "Damn those phone manufacturers. I was trying to send a text message, and it took me more than ten minutes to type a one-line message." I tried to calm him down. "But what is wrong? Why did it take you so long?" He continued, "Don't you see?! Their placement of the letters is so messed up? Why is 's' the 4th letter on its key? and 'e'? Why is it not the first letter on its key? I have to press '7' FOUR times to type an 's'? This is lunacy!"
教授loony,我的一个朋友，骂骂咧咧的来到我的办公室。他的脸变得很红，似乎也很生气。开口第一句话就是，妈的，那些该死的手机制造商。我发送一条短信，竟然拼写一行文字超过10分钟。我尝试让他冷静下来。那是贼莫拉？为甚麽用这麽长时间。他继续说，难道你没发现吗？他们把字母放的一团糟。为甚麽”s’是在这个键上第四个字母？还有’e’,为甚麽不是键上第一个字母？我必须按’7’四次才能拼写出’s’。真他妈愚蠢。
"Calm down, my friend," I said, "This scheme has been in use for so long, even before text messaging was invented. They had to keep it that way."
我说，兄弟，冷静下来吧。这种计划已经搞很长时间的，甚至早已文字被发明出来。他们也是没有办法的。
"That's not an excuse," his face growing redder and redder. "It is time to change all this. It was a stupid idea to start with. And while we are at it, how come they only put letters on 8 keys? Why not use all 12? And why do they have to be consecutive?"
他的脸变得更红啦，那不是借口。是时间去改变啦。开始就很愚蠢。当我们设计时，为甚麽要将字母放在仅仅8个键上呢？为甚麽不用所有的12个键呢？为甚麽字母非要连续设计呢？
"Umm... I... don't... know," I replied.
我回应道，呃，我也不知道。
"Ok, that's it. Those people are clearly incompetent. I am sure someone can come up with a better scheme."
“哦，就是这麽回事。那些人很显然很无能。我确信会有人设计出更好的方案。
He was one of those people, I could see. People who complain about the problem, but never actually try to solve it.
我发现，他就是这样一种人—去抱怨问题，而不去解决问题的人。
In this problem, you are required to come up with the best letter placement of keys to minimize the number of key presses required to type a message. You will be given the number of keys, the maximum number of letters we can put on every key, the total number of letters in the alphabet, and the frequency of every letter in the message. Letters can be placed anywhere on the keys and in any order. Each letter can only appear on one key. Also, the alphabet can have more than 26 letters (it is not English).
在这个挑战中，你被要求去想出最好的放置字母的方法使拼写被要求的文字的按键最小化。你将被给出键的数目，每一个键上方的最多字母数，每一个字母出现的频率。字母可以被放在键的任何地方和任何菜单中。每一个字母只能在一个键上出现一次。当然，字母总数会超过26个（非英语字母）。
For reference, the current phone keypad looks like this
仅供参考，过去的手机键是这样子的：
key 2: abc
key 3: def
key 4: ghi
key 5: jkl
key 6: mno
key 7: pqrs
key 8: tuv
key 9: wxyz
The first press of a key types the first letter. Each subsequent press advances to the next letter. For example, to type the word "snow", you need to press "7" four times, followed by "6" twice, followed by "6" three times, followed by "9" once. The total number of key presses is 10.
按键一次拼写出第一个字母。多按一次就向前递进一个。例如，去拼写字母“snow”你需要按7四次，跟着按6两次，然后按6三次，最后按9一次。总共需要10次。
Input
The first line in the input file contains the number of test cases N. This is followed by Ncases. Each case consists of two lines. On the first line we have the maximum number of letters to place on a key (P), the number of keys available (K) and the number of letters in our alphabet (L) all separated by single spaces. The second line has L non-negative integers. Each number represents the frequency of a certain letter. The first number is how many times the first letter is used, the second number is how many times the second letter is used, and so on.
输入：
输入中第一行是测试次数N。然后是N个测试。每一个测试包含2行。第一行有每一个键上放的最多字母P，有效键数目K和用空格分开的字母总数L。第二行有L个整数。每一个数代表一个字母出现的次数。第一个数字代表第一个字母被用的次数，以此类推。
Output
For each case, you should output the following
Case #x: [minimum number of keypad presses]
indicating the number of keypad presses to type the message for the optimal layout.
暗示优化后拼写整个信息所按的最少次数。
Limits
P * K ≥ L
0 ≤ The frequency of each letter ≤ 1 000 000
Small dataset
1 ≤ N ≤ 10
1 ≤ P ≤ 10
1 ≤ K ≤ 12
1 ≤ L ≤ 100
Large dataset
1 ≤ N ≤ 100
1 ≤ P ≤ 1 000
1 ≤ K ≤ 1 000
1 ≤ L ≤ 1 000
Sample
Input
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
Output
Case #1: 47
Case #2: 397
The story
Professor Loony, a dear friend of mine, stormed into my office. His face was red and he looked very angry. The first thing that came out of his mouth was "Damn those phone manufacturers. I was trying to send a text message, and it took me more than ten minutes to type a one-line message." I tried to calm him down. "But what is wrong? Why did it take you so long?" He continued, "Don't you see?! Their placement of the letters is so messed up? Why is 's' the 4th letter on its key? and 'e'? Why is it not the first letter on its key? I have to press '7' FOUR times to type an 's'? This is lunacy!"
教授loony,我的一个朋友，骂骂咧咧的来到我的办公室。他的脸变得很红，似乎也很生气。开口第一句话就是，妈的，那些该死的手机制造商。我发送一条短信，竟然拼写一行文字超过10分钟。我尝试让他冷静下来。那是贼莫拉？为甚麽用这麽长时间。他继续说，难道你没发现吗？他们把字母放的一团糟。为甚麽”s’是在这个键上第四个字母？还有’e’,为甚麽不是键上第一个字母？我必须按’7’四次才能拼写出’s’。真他妈愚蠢。
"Calm down, my friend," I said, "This scheme has been in use for so long, even before text messaging was invented. They had to keep it that way."
我说，兄弟，冷静下来吧。这种计划已经搞很长时间的，甚至早已文字被发明出来。他们也是没有办法的。
"That's not an excuse," his face growing redder and redder. "It is time to change all this. It was a stupid idea to start with. And while we are at it, how come they only put letters on 8 keys? Why not use all 12? And why do they have to be consecutive?"
他的脸变得更红啦，那不是借口。是时间去改变啦。开始就很愚蠢。当我们设计时，为甚麽要将字母放在仅仅8个键上呢？为甚麽不用所有的12个键呢？为甚麽字母非要连续设计呢？
"Umm... I... don't... know," I replied.
我回应道，呃，我也不知道。
"Ok, that's it. Those people are clearly incompetent. I am sure someone can come up with a better scheme."
“哦，就是这麽回事。那些人很显然很无能。我确信会有人设计出更好的方案。
He was one of those people, I could see. People who complain about the problem, but never actually try to solve it.
我发现，他就是这样一种人—去抱怨问题，而不去解决问题的人。
In this problem, you are required to come up with the best letter placement of keys to minimize the number of key presses required to type a message. You will be given the number of keys, the maximum number of letters we can put on every key, the total number of letters in the alphabet, and the frequency of every letter in the message. Letters can be placed anywhere on the keys and in any order. Each letter can only appear on one key. Also, the alphabet can have more than 26 letters (it is not English).
在这个挑战中，你被要求去想出最好的放置字母的方法使拼写被要求的文字的按键最小化。你将被给出键的数目，每一个键上方的最多字母数，每一个字母出现的频率。字母可以被放在键的任何地方和任何菜单中。每一个字母只能在一个键上出现一次。当然，字母总数会超过26个（非英语字母）。
For reference, the current phone keypad looks like this
仅供参考，过去的手机键是这样子的：
key 2: abc
key 3: def
key 4: ghi
key 5: jkl
key 6: mno
key 7: pqrs
key 8: tuv
key 9: wxyz
The first press of a key types the first letter. Each subsequent press advances to the next letter. For example, to type the word "snow", you need to press "7" four times, followed by "6" twice, followed by "6" three times, followed by "9" once. The total number of key presses is 10.
按键一次拼写出第一个字母。多按一次就向前递进一个。例如，去拼写字母“snow”你需要按7四次，跟着按6两次，然后按6三次，最后按9一次。总共需要10次。
Input
The first line in the input file contains the number of test cases N. This is followed by Ncases. Each case consists of two lines. On the first line we have the maximum number of letters to place on a key (P), the number of keys available (K) and the number of letters in our alphabet (L) all separated by single spaces. The second line has L non-negative integers. Each number represents the frequency of a certain letter. The first number is how many times the first letter is used, the second number is how many times the second letter is used, and so on.
输入：
输入中第一行是测试次数N。然后是N个测试。每一个测试包含2行。第一行有每一个键上放的最多字母P，有效键数目K和用空格分开的字母总数L。第二行有L个整数。每一个数代表一个字母出现的次数。第一个数字代表第一个字母被用的次数，以此类推。
Output
For each case, you should output the following
Case #x: [minimum number of keypad presses]
indicating the number of keypad presses to type the message for the optimal layout.
暗示优化后拼写整个信息所按的最少次数。
Limits
P * K ≥ L
0 ≤ The frequency of each letter ≤ 1 000 000
Small dataset
1 ≤ N ≤ 10
1 ≤ P ≤ 10
1 ≤ K ≤ 12
1 ≤ L ≤ 100
Large dataset
1 ≤ N ≤ 100
1 ≤ P ≤ 1 000
1 ≤ K ≤ 1 000
1 ≤ L ≤ 1 000
Sample
Input
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
Output
Case #1: 47
Case #2: 397
