403184: GYM101063 B Martian Sunrise

Life on a different planet is hard. It is usually all about science, research and cold nights and days. It is no different on Mars.

To entertain people, GEMA brought with the mission a group of talented musicians to write ballads about the new and exciting world. They were instructed to write a very long and optimistic song called Martian Sunrise and play it all day around the research and living facilities.

No musician could write, alone, a song with thousands of notes, so they divided their task. GEMA was on a tight budget, and ended up hiring musicians that can only write and play songs in their own favourite single key signature. A key signature is a set (out of 16 possible sets) of notes that can be used. In the end, the ballad was composed of different parts in various key signatures.

Now that cash is flowing in, the high commanders have decided to bring new, more talented musicians that can play up to two different key signatures to play the Mars Jam. It was decided that the musicians will take turns playing, and no musician will play again after having finished their part. GEMA has all the musicians on Earth at their disposal, since the mission is very highly regarded. This means that for any pair of key signatures, they can find infinitely many musicians that can play it.

Even with endless cash, it is good to be optimal. It is up to you to figure out the minimum number of musicians necessary to play the whole song.

The input will begin with an integer M, the number of existing key signatures (1 ≤ M ≤ 16). The next M lines of the input will be composed of a set of 7 words each, denoting the notes used in this signature. The words representing notes will have a maximum of two characters each, and will be in the format [A-G][b#]?, that is, start with an uppercase character between 'A' and 'G' and optionally have a '#' or a 'b', for a sharp or flat.

The next line of the input contains an integer N (1 ≤ N ≤ 10⁴). The following line contains the N notes of the original Martian Sunrise, separated by a space. Every note of the song is present in at least one of the M key signatures.

Please note that, although in musical terms C# equals Db, in this problem a musician that can play C# cannot necessarily play Db.

Output the minimum number of musicians necessary to play the Martian Sunrise.

10
C# D# E# F# G# A# B#
Cb Db Eb F Gb Ab Bb
C# D# E F# G# A B
C D E F G A B
C D E F# G A B
C D Eb F G A Bb
C# D E F# G# A B
C D E F G A Bb
C Db Eb F G Ab Bb
C# D# E# F# G# A# B
3
F# Bb B#

1

8
Cb Db Eb F Gb Ab Bb
C# D# E F# G# A# B
C# D# E# F# G# A# B
C D Eb F G Ab Bb
C# D# E# F# G# A# B#
C Db Eb F Gb Ab Bb
C D E F# G A B
C# D E F# G A B
6
C F# G# D B# Db

2