하리 머르데카

말레이시아의 독립기념일은 하리 머르데카라고 부른다. 1957년 말라야 연방이 영국 식민 통치에서 벗어난 것을 기념해 매년 8월 31일에 열린다. 8월 한 달 동안 많은 말레이시아 사람이 집 발코니와 자기가 가진 탈것에 국기를 단다. 유모차도 예외가 아니다. 이날 행사에서는 "Merdeka!"를 일곱 번 외친다.

내년 독립기념일을 앞두고 IIUM은 본교 캠퍼스 둘레에 긴 배너를 걸기로 했다. 준비 위원회는 학생과 교수에게 힘이 되는 문구를 이 배너에 쓰려고 한다. 조건은 두 가지다. 모든 단어를 띄어쓰기 없이 한 줄로 이어 쓴다. 그리고 단어끼리 겹쳐도 된다. 예를 들어 WORDER 안에는 WORD와 ORDER가 들어 있다. 아래에서는 배너에 적힌 문자열을 텍스트라고 부른다.

위원회는 단어 목록을 만들고 각 단어에 점수를 매겼다. 텍스트의 점수는 단어가 텍스트에 나타난 횟수마다 그 단어의 점수를 더한 값이다. WORD의 점수가 5이고 ORDER의 점수가 8이면 텍스트 WORDER의 점수는 $5 + 8 = 13$이다. 텍스트 WORDWORDER에서는 WORD가 두 번 나타나므로 점수가 $5 + 5 + 8 = 18$이다.

위원회는 텍스트의 글자를 하나하나 손으로 만들려고 한다. 글자를 하나 만들 때마다 비용이 들고 위원회의 예산은 정해져 있다.

예산을 넘지 않으면서 점수가 가장 높은 텍스트를 찾아라. 텍스트 자체는 출력하지 않고 그 점수만 출력하면 된다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($T \le 30$)

각 케이스의 첫 줄에는 세 정수 $N$, $M$, $B$가 주어진다. $N$은 쓸 수 있는 문자의 개수, $M$은 단어의 개수, $B$는 예산이다. ($1 < N \le 26$, $1 \le M \le 100$, $10 \le B \le 200$)

다음 $N$개의 줄에는 문자 $H_i$와 정수 $C_i$가 주어진다. $H_i$는 A부터 Z까지 중 하나이고, $C_i$는 텍스트에 $H_i$를 하나 쓰는 비용이다. ($1 \le C_i \le 3$) $H_i$는 모두 서로 다르다.

이어지는 $M$개의 줄에는 단어 $W_i$와 정수 $S_i$가 주어진다. $S_i$는 그 단어의 점수다. ($1 \le |W_i| \le 100$, $1 \le S_i \le 100$)

단어에 나오는 문자는 모두 $H_i$ 중에 있다. 텍스트에는 주어진 $N$개의 문자만 쓸 수 있고, 텍스트의 비용은 쓴 글자 하나하나의 비용을 모두 더한 값이다.

각 케이스마다 Case #X: Y 형식으로 한 줄씩 출력한다. $X$는 1부터 시작하는 케이스 번호이고, $Y$는 그 케이스에서 얻을 수 있는 가장 높은 점수다. 예산 안에서 어떤 단어도 나타나게 할 수 없으면 0을 출력한다.

첫 번째 예제의 첫 케이스에서 점수가 가장 높은 텍스트는 AAAAA다. AA가 네 번, AAA가 세 번 나타나므로 점수는 $4 \times 10 + 3 \times 30 = 130$이다. AAAAA를 쓰려면 A가 다섯 개 필요하고 A 하나의 비용이 2이므로 전체 비용은 10이다.