33107번 - The Journey of the King 다국어

You are very close to becoming the King of Games. The only thing left to do is to win in a card game against the incarnation of the King of Nusantara, Anda, whose soul resides inside you as your split personality.

Each player has a deck of cards, each card contains a word. Within each deck, there are no two cards containing the same word. There is also a dictionary consisting of $D$ distinct words: $[W_1, W_2, \dots , W_D]$.

The game consists of $N$ turns. In turn $i$, Anda will play a card with the word $A_i$. Then, you can either match his card with one of your remaining cards or skip this turn. Two cards, $a$ and $b$, match if either the words $a + b$ or $b + a$ exist in the dictionary. The operator $+$ represents the concatenation operation. For instance, the concatenation of words AU and RA is AU $+$ RA $=$ AURA. Once you match a card, you cannot use that card for the rest of the game.

Your deck has $M$ cards (numbered from $1$ to $M$); card $j$ contains word $B_j$. You want to maximize the number of turns in which you successfully match Anda’s card.

The first line consists of an integer $D$ ($1 ≤ D ≤ 200\, 000$).

Each of the next $D$ lines consists of a string $W_k$. String $W_k$ consists of only uppercase English letters. The sum of length of $W_k$ does not exceed $200\, 000$. It is guaranteed that $W_k \ne W_{k'}$ for $1 ≤ k < k' ≤ D$.

The following line consists of an integer $N$ ($1 ≤ N ≤ 100\, 000$).

Each of the next $N$ lines consists of a string $A_i$. String $A_i$ consists of only uppercase English letters. The sum of length of $A_i$ does not exceed $100\, 000$. It is guaranteed that $A_i \ne A_{i'}$ for $1 ≤ i < i' ≤ N$.

The following line consists of an integer $M$ ($1 ≤ M ≤ 100\, 000$).

Each of the next $M$ lines consists of a string $B_j$. String $B_j$ consists of only uppercase English letters. The sum of length of $B_j$ does not exceed $100\, 000$. It is guaranteed that $B_j \ne B_{j'}$ for $1 ≤ j < j' ≤ M$.

Output a single integer representing the maximum number of turns you match Anda’s card.