Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1639
Hang Up the System

Time Limit: 2 Seconds      Memory Limit: 32768 KB

You're going to design a multi-task operating system for an embedded system. Because the resources are limited on this mini computer, parallel running of some programs will probably give rise to the deadlock problem. According to experience, you have a list of programs that will hang up the system if all of them are running simultaneously. You are also given the priority of these programs. Now you're interested in the maximum value of the total priority of the programs that can run simultaneously in the system without hanging up.


Input

The input has several test cases, each starts with n (2 <= n <= 16), the number of programs. The following n lines contain the name of the program and its priority, with each program on a line. The name is a string of no more than 10 characters. The priority is an integer from 1 to 100. The next line contains a single integer m (0 <= m <= 1,024), which is the length of the list of the conflicting programs. The following m lines each contains several names of the programs which cannot run together.

The input is terminated with a case n = 0. This case should not be processed.


Output

Print the case number and the maximal total priority value you can get on a line. Adhere to the sample output format.


Sample Input

3
HARDDISK 20
FLOPPY 10
CDROM 15
1
CDROM HARDDISK
5
HARDDISK 20
FLOPPY 10
CDROM 15
SERIAL 25
MOUSE 20
3
CDROM HARDDISK FLOPPY
FLOPPY SERIAL
SERIAL MOUSE
0


Sample Output

System 1: 30
System 2: 60



Author: TANG, Jiqing
Source: Zhejiang University Local Contest 2003
Submit    Status