Text Messaging Outrage (Small)

Professor Loony, a friend of mine, stormed into my office with a red face. The first thing he said was, "I cannot stand those phone manufacturers. I tried to send a one-line text message and typing it took me more than ten minutes." I tried to calm him down. "What is wrong? Why did it take you so long?" He went on, "Don't you see? Their placement of the letters is a mess. 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!"

"Calm down, my friend," I said. "This scheme has been in use since long before text messaging was invented. They had to keep it that way."

"That is not an excuse," he said, his face growing 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?"

"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 a problem but never try to solve it.

In this problem you find the letter placement that minimizes the number of key presses needed to type a message. You are given the number of keys, the maximum number of letters you 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 on any key and in any order. Each letter appears on one key only. The alphabet can have more than 26 letters (it is not English).

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 on it. Each further press advances to the next letter on that key. For example, to type the word "snow" you press '7' four times, then '6' twice, then '6' three times, then '9' once. The total number of key presses is 10.

The first line contains the number of test cases $N$. Then $N$ cases follow, and each case takes two lines.

The first line of a case has the maximum number of letters to place on a key $P$, the number of keys available $K$, and the number of letters in the alphabet $L$, separated by single spaces. The second line has $L$ non-negative integers. Each number is the frequency of one 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 the rest follow in the same order.

Limits

• $P \times K \ge L$
• The frequency of each letter is between 0 and 1,000,000
• $1 \le N \le 10$
• $1 \le P \le 10$
• $1 \le K \le 12$
• $1 \le L \le 100$

For each case, print one line in this format.

Case #x: y

Here $x$ is the 1-based case number and $y$ is the minimum number of key presses needed to type the message under an optimal layout.