Problem Description
Professor Binns has finally got tired of scoring essays himself and implemented an automatic essay scoring system to help him screen the numerous essays. Strongly against such an idea, you decided to generate a meaningless essay which can get high mark in his system to prove that his system does not work at all. You've obtained the rules used by Binns's system to score the essay, they're as follows:
a) The word in the essay must be from a particular set of words. If not, the essay will receive a score zero and is automatically rejected.
b) Every word in the specified set has a positive integer associated with it, indicating the score the submitter will get for using that word once.
c) A word can be used in several different ways; for example, in English, the word “word” can be used as both a noun and a verb. Every occurrence of specific patterns (like verb – adjective – noun) will earn the submitter a particular score.
In particular, it is allowed for a word to be interpreted in different ways in different patterns.
You're interested in generating an essay of a specified length with maximum possible score.
Input
There are multiple test cases in the input file. Each test case starts with three integers N, M and K, (1 <= N <= 100, 0 <= M <= 8, 0 <= K <= 6), the length of the essay to generate, the number of words in the dictionary and the number of patterns, respectively. The following M lines describe the words in the dictionary; each line consists of two integers, Wi, and Ti, (0 <= Wi <= 2000, 1 <= Ti <= 5), representing the score submitter gets every time he/she uses the word, and the number of ways the word can be used. The next part of the input describes the patterns. Each of the K lines describes one pattern, beginning with two integers, Wi, and Ci, (0 <= Wi <= 2000, 1 <= Ci <= 6), indicating the score one can get every time the pattern is used, and the number of consecutive parts in the pattern; followed by Ci integers describing the language parts in the pattern. It is guaranteed that the total number of ways to use a word does not exceed 5; furthermore, the total number of parts contained in all patterns (sum of all Cis) will not exceed 25.
There is a blank line after each test case. Input ends with End-of-File.
Output
For every test case, you should output one integer on a separate line, the maximum score one can get, in the format as indicated in the sample output.
Sample Input
2 3 2
4 3 0 1 2
5 2 2 3
1 2 0 4
1 2 1 3
10 2 4 2
2 3 2
4 3 0 1 2
5 2 2 3
1 2 0 4
1 2 1 3
2 2 4 2
Sample Output
Case 1: 16
Case 2: 10
