Hang Up the System

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

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐