셔플 게임

셔플 게임은 딜러와 플레이어가 함께 하는 간단한 카드 게임이다. 처음에 같은 덱 $n$장이 딜러와 플레이어에게 똑같이 주어진다. 덱의 각 카드는 무늬 C, D, H, S 중 하나와 숫자 2, 3, 4, 5, 6, 7, 8, 9, 10, A, J, K, Q 중 하나로 이루어진다. 따라서 카드는 52종류이며, 같은 카드가 덱에 여러 장 있을 수 있다.

카드를 받은 뒤 딜러는 임의의 셔플 방법으로 자신의 덱 $X$를 만들어 플레이어에게 보여준다. 이후 플레이어는 다음 과정으로 덱 $Y$를 만든다. $Y$는 처음에 비어 있다.

• 1단계. 플레이어가 받은 덱으로 덱 $P_1$과 $P_2$를 만든다. 두 덱의 카드 수는 달라도 된다.
• 2단계. $P_1$과 $P_2$를 끼워 넣는다(인터리브). 즉 $P_1$ 또는 $P_2$의 맨 아래 카드를 $Y$의 현재 맨 위로 옮기는 일을 두 덱에 카드가 모두 없어질 때까지 반복한다. 플레이어가 $P_1$과 $P_2$의 카드를 번갈아 옮길 필요는 없다. 딜러와 플레이어는 같은 $n$장의 카드에서 각자의 덱을 만들므로, $Y$는 언제나 $X$와 같은 카드로 이루어진다.

덱은 아래에서 위 순서로 나열한 카드열로 표기한다. 플레이어의 점수는 두 카드열 $X$와 $Y$의 최장 공통 부분 수열(LCS)의 길이다.

예를 들어 $n = 5$인 덱 (C2, CJ, D5, HA, S7)이 두 사람에게 주어졌다고 하자. 딜러는 $X =$ (CJ, D5, HA, C2, S7)을 만들어 플레이어에게 보여준다. 플레이어는 $P_1 =$ (D5, HA)와 $P_2 =$ (CJ, S7, C2)를 만든 뒤, 이를 끼워 넣어 $Y =$ (D5, CJ, S7, HA, C2)를 만든다. 이때 (CJ, HA, C2)가 최장 공통 부분 수열이므로 점수는 3이다. 같은 $P_1$과 $P_2$로 $Y =$ (CJ, D5, HA, S7, C2)를 만들면 점수는 4가 된다.

$n$, $X$, $P_1$, $P_2$가 주어질 때, 2단계 이후 플레이어가 얻을 수 있는 최대 점수를 구하라.

첫 줄에 양의 정수 세 개 $n$, $p$, $q$가 주어진다($3 \le n \le 500$, $p + q = n$). $n$은 처음 덱의 카드 수이고, $p$와 $q$는 각각 $P_1$과 $P_2$의 카드 수이다. 다음 세 줄에는 딜러의 덱 $X$($n$장), 플레이어의 덱 $P_1$($p$장), $P_2$($q$장)가 차례로 주어진다. 각 카드는 무늬를 나타내는 대문자 알파벳(C, D, H, S 중 하나) 다음에 숫자(2, 3, 4, 5, 6, 7, 8, 9, 10 또는 대문자 A, J, K, Q 중 하나)가 붙어서 표기된다. 같은 줄의 카드는 해당 덱의 아래에서 위 순서로 나열된다.

2단계 이후 $X$, $P_1$, $P_2$로부터 플레이어가 얻을 수 있는 최대 점수를 한 줄에 출력한다.