H :: IGPC

Time Limit: 3 Seconds Memory Limit: 65536 KB

As more people are participating in IGPC (International Gossipful Programming Contest) and more people are watching the results, cheating in the contest has become very hard these days. But as we all know, Bahman is a very good cheater and all these years, he has managed to fool every single person involved in IGPC.
Bahman is the network administrator of the place where contest will be held. So it is easy for him to cheat in the contest as all the submissions will go throgh the network. But couple of weeks ago, a brave detective showed up and released some evidence which indicated that someone is cheating in the IGPC!
Luckily, Bahman knows exactly who this detective is and he knows all of his friends and his personality. So he can map the activities of the detective’s brain and try to cheat in a way that the detective doesn’t notice.
For the final round of these contests, it has been decided that the certificates be issued only for high rank teams. Teams with more than 3 solved problems will be counted as high rank. So it came to Bahman’s mind that he can cheat and change the results of the teams so one team doesn’t get the certificate and another team does.
The detective has some predictions. If any of those predictions doesn’t come true, he immediately publishes more convincing evidence about cheating in IGPC. His predictions are in the form of one of these sentences:

At least one of TeamX or TeamY should get a high rank. At least one of TeamX or TeamY should get a low rank. TeamX and TeamY should get the same rank. TeamX and TeamY should not get the same rank. Both TeamX and TeamY should get a high rank. Both TeamX and TeamY should get a low rank.

On the other hand, Bahman receives lots of requests from teams and their coaches and even the observers who want to cheat in the contest. Requests are in the form of one of these sentences:

I will pay you D dollars if TeamX and TeamY get a high rank. I will pay you D dollars if TeamX and TeamY get a low rank. I will pay you D dollars if TeamX gets a high rank and TeamY gets a low rank. I will pay you D dollars if TeamX gets a low rank and TeamY gets a high rank.

Now, as you may already know, Bahman wants to cheat and change the result of some submissions from "accpeted" to "wrong answer" or from "wrong answer" to "accepted", to give some teams a high or low rank. He may also submit a code on behalf of a team. But according to the requests, he wants to get as much money as he can and at the same time, he should watch out and be careful not to break any of the detective’s predictions.

Input

The input contains several test cases.
In the first line of input comes T (0 < T ≤ 25), the number of test cases.
In the first line of each test, there is an integer n (0 ≤ n ≤ 100), the number of teams. In the next line there is an integer r (1 ≤ r ≤ 5000) which is the number of cheating requests. Each of the next r lines contains the description of a cheating request as described above (0 ≤ D < 64). The next line contains the integer p (0 ≤ p ≤ 100), the number of predictions. In the following p lines, there will be one prediction in each line as noted earlier.
Team names contain only English alphabets and numbers, are case-sensitive and at most 15 characters in length.

Output

For each test case, output the maximum profit that Bahman can get by manipulating the results, while not breaking any of the detective’s predictions.
If there is no possible way to not break the predictions, just print “Haters gonna hate anyway!” in one line.

Sample Input

2
3
2
I will pay you 9 dollars if BMP gets a high rank and HereForPunch gets a low rank.
I will pay you 7 dollars if MASSters and MASSters get a high rank.
2
HereForPunch and MASSters should not get the same rank.
At least one of BMP or MASSters should get a low rank.
10
1
I will pay you 50 dollars if HereForLunch and ZoMbeeZ get a high rank.
2
Both HereForLunch and ZoMbeeZ should get a high rank.
Both 0x00 and HereForLunch should get a low rank.

Sample Output

7
Haters gonna hate anyway!

Submit

Source: 12th Iran Nationwide Internet Contest - Final