Hari Merdeka

Malaysia's Independence Day is called Hari Merdeka. It falls on 31 August every year and marks the independence of the Federation of Malaya from British colonial rule in 1957. Through the whole month of August many Malaysians raise the national flag on the balcony of their home and on every vehicle they own, baby strollers included. At the celebration people shout "Merdeka!" seven times.

For next year's Independence Day, IIUM will hang a long banner around its main campus. The organising committee wants to write words on the banner that encourage the students and the professors. Two rules apply. All words go on one single line with no spaces between them. Words are allowed to overlap each other. For example, WORDER contains the words WORD and ORDER. Whatever ends up on the banner is called the text.

The committee compiled a list of words and gave each word a score. The score of the text is the sum of the score of each word once for every occurrence of that word in the text. If WORD is worth 5 and ORDER is worth 8, then the text WORDER scores $5 + 8 = 13$. In the text WORDWORDER the word WORD occurs twice, so it scores $5 + 5 + 8 = 18$.

The committee also wants every character in the text handcrafted. Crafting one character costs money and the committee's budget is fixed.

Find the text with the highest score whose cost stays within the budget. Do not print the text itself, only its score.

The first line contains an integer $T$, the number of cases. ($T \le 30$)

Each case starts with a line holding three integers $N$, $M$ and $B$: the number of characters, the number of words, and the committee's budget. ($1 < N \le 26$, $1 \le M \le 100$, $10 \le B \le 200$)

The next $N$ lines each contain one character $H_i$ from A to Z and one integer $C_i$, the cost of writing one $H_i$ in the text. ($1 \le C_i \le 3$) All $H_i$ are distinct.

The following $M$ lines each contain one word $W_i$ and one integer $S_i$, the score of that word. ($1 \le |W_i| \le 100$, $1 \le S_i \le 100$)

Every character used in the words appears among the $H_i$. The text may use only those $N$ characters, and the cost of the text is the sum of the cost of every character written in it.

For each case print one line in the form Case #X: Y, where $X$ is the case number starting from 1 and $Y$ is the highest score obtainable in that case. If no text within the budget contains any word, print 0.

In the first case of the first example the best text is AAAAA. It contains AA four times and AAA three times, so the score is $4 \times 10 + 3 \times 30 = 130$. Writing AAAAA needs five copies of A at a cost of 2 each, so the total cost is 10.