Guernica is a famous painting by Pablo Picasso, depicting the bombing of the Basque town of Guernica during the Spanish Civil War. It shows the tragedies war inflicts upon individuals, particularly innocent civilians. The work has gained a monumental status, becoming a perpetual reminder of the tragedies of war, an anti-war symbol and an embodiment of peace.

After you were told that the painting was moved from the Museo del Prado to the Museo Nacional Centro de Arte Reina Sofia in 1992, you are on your way to that place. At your arrival, a creepy sight awaits you: Malicious vandals have cut the Guernica painting into several pieces and distributed them throughout the whole museum. A team already gathered all N pieces they could find. All these pieces have the same dimensions! Observing the dimensions, they conclude that there are far too many pieces to rebuild only Guernica. The vandals did in fact not only disassemble the original painting by Picasso but also several copies of it! Exactly P pieces are needed to reconstruct Guernica (or any of its copies).

Now experts have to evaluate how probable it is that sets of P pieces belonged to one and the same initial painting and assigned each such combination a matching score. By maximizing the total matching score, they would be able to determine which pieces belonged to the same initial painting. Can you help them calculating the overall maximum matching score for all of the paintings?

Input

The input consists of several test cases (T≤10), each of which starts by 3 integers on a line: the number of pieces found N, the number of pieces per painting P and Z, the number of possible combinations. (P, N≤15, Z≤1’000) The next Z lines each contains P+1 positive integers (i1, i2, …, iP, s), that means a score of s is given to the combination (i1, i2, …, iP). (i1,..,iP ≤N, 0<s<10’000) The last test case is followed by a single line with 3 zeros, which should not be processed.

Output

For each test case, print the case number and the largest score. If it is impossible to group all pieces so that entire paintings result out of them, print -1.

Example

Input:
9 3 3
1 2 3 1
4 5 6 2
7 8 9 3
9 3 4
1 2 3 1
1 4 5 2
1 6 7 3
1 8 9 4
3 3 1
1 2 3 9
5 4 1
2 1 5 3 10
0 0 0

Output:
Case 1: 6
Case 2: -1
Case 3: 9
Case 4: -1