Batman, the superhero, has difficult days fighting villains, and today is one of these days. Batman begins the day checking the list of superpowers that he can use to beat the enemies of Gotham City, and the list of villains that he has to beat during the day.
Each superpower has a name, an attack factor and an energy consumption in calories. Each villain has an alias, a defense factor, and the list of the names of the superpowers that can affect him. To beat a specific villain, Batman must attack him with a superpower that can affect the villain and whose attack factor is greater or equal than the defense factor of the villain. Besides, Batman must use the powers of his list in order (possibly skipping some powers) and have to beat all the villains in the same order of the list. Like everybody else, Batman doesn't have unlimited energy ... he can only spend maximum E calories per day.
Given a list of superpowers and a list of villains, is it possible that Batman beats them all without spending more than E calories?
The input consists of several test cases. Each test case is represented as follows:
- A line with three integers P, V and E (0
P,V
1000, 0
E 108
), representing (respectively) the number of superpowers, the number of villains and the maximum amount of calories that Batman can spend per day.
- P lines, one per superpower, containing the following information separated by spaces:
- An alphanumeric string s
with the name of the superpower (case sensitive, without spaces).
- An integer a
(0
a
10000) specifying the attack factor of the superpower.
- An integer c
(0
c
100000) specifying the energy consumption in calories of the superpower.
- V lines, one per villain, containing the following information separated by spaces:
- An alphanumeric string s
with the alias of the villain (case sensitive, without spaces).
- An integer d
(0
d
10000) specifying the defense factor of the villain.
- A list with the names of the superpowers that can affect the villain, separated with commas. The list will not contain repeated names.
The end of the input is specified by a line with the string ``0 0 0''.
Suppose that the superpowers have distinct names and that the villains have distinct aliases.
The maximum length of a name or alias is 100 characters and the minimum length of a name or alias is 1 character.
For each test case, print the line ``Yes'' if it's possible for Batman to beat all the villains spending E or less calories. Otherwise, print the line ``No''.
4 3 1200
A 8000 500
B 7000 600
C 9000 400
D 5000 300
Joker 6000 B,A
Penguin 8000 B,C,D
TwoFace 5000 D,A,B,C
4 3 1000
A 8000 500
B 7000 600
C 9000 400
D 5000 300
Joker 6000 B,A
Penguin 8000 B,C,D
TwoFace 5000 D,A,B,C
0 0 0
Yes
No
Colombia'2008