Shuffle Game

Shuffle Game is a simple card game between the dealer and the player. At the start, the same deck of $n$ cards is given to both the dealer and the player. Each card has a suit, one of C, D, H, or S, followed by a kind, one of 2, 3, 4, 5, 6, 7, 8, 9, 10, A, J, K, or Q. So there are 52 different cards, and the same card can appear more than once in a deck.

After the cards are dealt, the dealer builds their own deck $X$ from the dealt cards using any shuffling method and shows $X$ to the player. Then the player builds a deck $Y$ as follows. $Y$ starts empty.

• Step 1. Build two decks $P_1$ and $P_2$ from the deck the player was given. The two decks can have different sizes.
• Step 2. Interleave $P_1$ and $P_2$. That is, repeatedly move the bottom card of $P_1$ or the bottom card of $P_2$ onto the current top of $Y$, until both $P_1$ and $P_2$ are empty. The player does not have to alternate between $P_1$ and $P_2$. Both the dealer and the player build their decks from the same $n$ cards, so $Y$ always contains the same cards as $X$.

A deck is written as its sequence of cards from bottom to top. The player's score is the length of the longest common subsequence (LCS) of the sequences $X$ and $Y$.

For example, suppose the deck (C2, CJ, D5, HA, S7) with $n = 5$ is given to both players. The dealer builds $X =$ (CJ, D5, HA, C2, S7) and shows it to the player. The player builds $P_1 =$ (D5, HA) and $P_2 =$ (CJ, S7, C2), then interleaves them into $Y =$ (D5, CJ, S7, HA, C2). The score is 3, because (CJ, HA, C2) is a longest common subsequence of $X$ and $Y$. However, the player can interleave the same $P_1$ and $P_2$ into $Y =$ (CJ, D5, HA, S7, C2), which gives a score of 4.

Given $n$, $X$, $P_1$, and $P_2$, compute the maximum score the player can achieve after Step 2.

The first line contains three positive integers $n$, $p$, and $q$ ($3 \le n \le 500$, $p + q = n$), where $n$ is the number of cards in the initial deck, and $p$ and $q$ are the numbers of cards in $P_1$ and $P_2$. The next three lines contain the dealer's deck $X$ with $n$ cards, and the player's decks $P_1$ with $p$ cards and $P_2$ with $q$ cards. Each card is written as its suit (an uppercase letter C, D, H, or S) followed by its kind (2, 3, 4, 5, 6, 7, 8, 9, 10, or the uppercase letter A, J, K, or Q). The cards on each line are listed from the bottom to the top of the corresponding deck.

Print one line containing the maximum score the player can achieve from $X$, $P_1$, and $P_2$ after Step 2.