Minimum Keypresses for Text Entry

A phone keypad puts several letters on one key and tells them apart by how many times you press it. The first press types the first letter on that key, and each press after that moves one letter further along the same key.

The layout in use today 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

With this layout, typing "snow" takes four presses of 7, two presses of 6, three presses of 6 and one press of 9, so the total is 10 presses. The letter s sits fourth on key 7, which is why it costs four presses, and a frequent letter placed near the end of a key inflates the count that way.

Now design the layout from scratch. You are given the maximum number of letters allowed on one key, $P$, the number of keys available, $K$, the size of the alphabet, $L$, and how many times each letter is used in the message. Any letter may go on any key in any position, whatever the alphabetical order, and each letter goes on exactly one key. The alphabet may hold more than 26 letters.

Compute the smallest number of presses needed to type the whole message.

The first line holds the number of test cases, $N$. Then come $N$ cases. Each case takes two lines. The first line holds the maximum number of letters on one key, $P$, the number of keys, $K$, and the size of the alphabet, $L$, separated by single spaces. The second line holds $L$ non-negative integers, where the $i$-th number is how many times the $i$-th letter is used in the message.

Limits

• $P \times K \ge L$
• $1 \le N \le 100$
• $1 \le P \le 1\,000$
• $1 \le K \le 1\,000$
• $1 \le L \le 1\,000$
• each letter is used between $0$ and $1\,000\,000$ times

For each case, print one line in this format.

Case #x: y

Here $x$ is the case number starting from $1$, and $y$ is the minimum number of presses needed to type the message under an optimal layout.