시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 256 MB | 13 | 7 | 7 | 58.333% |
Malaysia’s Independence Day -- also known as Hari Merdeka -- is celebrated each year on 31 August to commemorate the independence of Federation of Malaya from British colonial rule in 1957. During the whole month of August, many Malaysians express their patriotisms and loves toward their country by raising Malaysian flag on their home’s balcony and on any vehicles they have (baby stroller included). This independence day celebration is usually incomplete without shouting “Merdeka!” seven times.
For the next year Independence Day celebration, IIUM plans to put up a long banner around IIUM’s main campus. The committees want to write meaningful and motivating words in this banner to inspire students (and possibly professors too). To make things interesting, they agree that all words should be written without spaces in one single line. Moreover, they also agree that words are allowed to overlap each other. For example, “WORDER” contains the words: “WORD” and “ORDER”. For ease of explanation, let say whatever is written on the banner as text.
The committees have compiled a list of words and assigned each word with a score which will be counted as the text’s score for every occurrence of such word in the text. For example, if the value of WORD is 5 and ORDER is 8, then the text WORDER has a score of 5 + 8 = 13; WORDWORDER has a score of 5 + 5 + 8 = 18 (notice that WORD occurs twice in this example).
Aside from words, the committees also want each character in the text to appear as fancy as possible, thus, each written character will be specially handcrafted. Of course this cause another problem: handcrafting each character requires additional cost and obviously the committees’ budget is limited.
Your task in this problem is to help the committees to determine what text should be written on the banner such that its score is as high as possible while the cost of writing such text is within the given budget. To make things easier, you only need output the score.
The first line contains an integer T (T ≤ 30) denoting the number of cases. Each case begins with three integers in a single line: N (1 < N ≤ 26), M (1 ≤ M ≤ 100) and B (10 ≤ B ≤ 200) denoting the number of characters, the number of words, and the committees’ budget. The next N following lines each contain one character Hi (A-Z) and one integer Ci (1 ≤ Ci ≤ 3) which represent the cost of writing one character Hi in the text. You may assume Hi are unique for all i = 1..N. The following M lines each contain one word Wi (1 ≤ |Wi| ≤ 100) and one integer Si (1 ≤ Si ≤ 100) denoting the score of such word. Assume all characters in the given set of words exists among Hi.
For each case, output “Case #X: Y” (without quotes) in a line where X is the case number, starting from 1, followed by a single space, and Y is the highest possible score which can be obtained in the corresponding case.
2 3 3 10 A 2 B 2 C 3 AA 10 AAA 30 ABC 60 14 8 200 M 2 I 3 R 2 A 1 O 2 E 2 C 2 L 2 F 1 V 2 Y 3 H 1 U 2 N 2 MIRACLE 100 FLUFFY 40 LOVE 100 IVY 10 VEN 30 AYE 20 HOE 10 EURO 80
Case #1: 130 Case #2: 2600
The text with highest score is AAAAA. There are 4 occurrences of AA and 3 occurrences of AAA, which makes the score to be 4 * 10 + 3 * 30 = 130. Writing AAAAA requires 5 A each costs 2, thus the total cost is 10.