Jinyuetuan Puzzle

JinYueTuan is a famous online game which has been in vogue for a long time. Large number of players put themselves in it day after days…

JinYueTuan is a simple game with these rules:
Only seven keys on the keyboard will be used in games, each key are assigned to one of the seven sound tracks. During the game, a series of notes may fall in each sound track irregularly. When notes fall down in one sound track, player should press the assigned key at once. If so, then got a “Cool”, or get “Miss” otherwise.

There are two types of “Note”: “single note” and “strip note”. Just as the name implies, “single note” means a single note, press right key at the right time once, then you can get a “Cool”, otherwise “Miss”; “strip note” needs you keeping press the corresponding key from the start time to the end time of the note. Press key at the begin time you may get a “Cool”, and release at the end time to get another “Cool”, you will “Miss” either early or late. If “Miss” at the begin time, then “Miss” the other (the end time) immediately.

People lament about the fact that such an easy game is limited by the hardware design, the so-called “keys confliction”. “keys confliction” means some key combinations cannot be pressed. For example, when Track 1,4,5,6 fall a note at the same time respectively, we should press the four keys at the same time, but now, keys confliction may happen, and cause this to fail, then you will “Miss” all these four notes. Keys confliction meets the relation of inclusion, in other words, if keys set S would cause the confliction, so would keys set T when S is included in T. Note that, if at a certain moment in time, some keys should be pressed and some pressing keys should be released, then you can release and press at the same time, and released keys won’t cause any keys confliction at all.

Because of the keys confliction, we have to give up some notes to save as more other notes as possible. More details will be explained in the sample data.

Now you know the falling time and type (single or strip) of each note in each sound track, and all keys-assembling that may cause confliction. Your task is to calculate the maximum number of “Cool” that player can get.

There are multiple test cases, the number of them T is given in the very first line, followed by T cases.

For each test case:
First line contains an integer N, the length of the music (1≤N≤1000).
The next 7 lines will contain description of each sound track. The first number in each line, C, denote the number of notes in that sound track. Following C description of each note: A single number “A” denotes an single note at Time A(1≤A≤N); A pair of integers separating by ‘-’,”A-B” denotes a strip note start at Time A and end at Time B(1≤A<B≤N). In each sound track, no superposition exists, no strip starts at another’s end time, no single notes puts in a strip(includes begin and end point).

The next line contain a single integer K (0≤K<2⁷), denotes K descriptions of Keys Confliction are following.

Each description is a single line containing a string of seven characters S0 S1 S2…S6, if Sk1,Sk2,…,Sks were character ‘1’ and others were ‘0’, that means key combination Sk1Sk2…Sks may cause Keys Confliction.

For each test case, output one line containing integer P with case number, the maximum number of “Cool” players can get.

3
6
3 1 3 4
2 1 2-5
2 3 6
0
0
0
0
1
1110000
6
3 1 3 5
2 1 2-5
2 5 6
0
0
0
0
1
1110000
6
1 1
1 1-3
1 1
0
0
0
0
1
1110000

Case #1: 7
Case #2: 8
Case #3: 3

2009 Asia Shanghai Regional Contest Host by DHU