시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 512 MB 17 7 6 54.545%

문제

밥은 루미큐브 게임을 즐겨한다. 밥이 가진 카드와 테이블에 이미 내어져 있는 카드들을 모두 알고 있을 때, 밥이 낼 수 있는 카드 개수의 최댓값을 출력하시오.

루미큐브의 게임 규칙은 다음과 같다. 

  1. 루미큐브는 1부터 7까지의 숫자가 적힌 4가지 색깔 (blue, red, yellow, black)의 카드로 하는 게임으로, 총 28개의 카드로 게임을 한다.
  2. 특정 숫자와 특정 색깔을 가진 카드는 정확히 하나 존재한다.
  3. 밥이 카드를 낼 때, 테이블에 내어진 카드들이 루미큐브세트들로 구성되도록 해야 한다.
  4. 루미큐브세트에는 그룹과 연속이 있다. 그룹은 색이 다르지만 숫자는 같은 카드 3개나 4개를 말하고, 연속은 색이 같고 숫자가 연속되는 3개 이상의 카드를 말한다. 
  5. 테이블에 내어진 카드들이 루미큐브세트로 구성되었다는 것은, 카드들을 적당한 묶음으로 분할해, 모든 묶음이 루미큐브세트를 이루도록 할 수 있다는 것이다.
  6. 밥이 카드를 낼 때, 루미큐브세트를 구성하기 위해서 테이블 위에 놓인 카드들을 활용할 수 있다. 테이블 위에 놓인 카드들은 여전히 루미큐브세트들로 구성되어야 한다.  

                          

입력

첫 줄에는 밥이 가지고 있는 카드의 개수 n이 주어진다. (1 ≤ n ≤ 28)

둘째 줄에는 밥이 가지고 있는 카드에 대한 정보가 사이에 공백을 두고 주어진다.

셋째 줄에는 테이블에 놓인 카드의 개수 m이 주어진다. (0 ≤ m ≤ 28-n)

넷째 줄에는 테이블에 놓인 카드에 대한 정보가 사이에 공백을 두고 주어진다. 

카드들에 대한 정보는 색(char형)숫자(int형)으로 주어진다. 예시 입출력을 참고하여라.

단, 테이블에 놓인 카드들은 루미큐브세트들로 구성되어 있음이 보장되며, 동일한 카드는 두 번 이상 입력되지 않는다.

출력

밥이 낼 수 있는 카드 개수의 최댓값을 출력한다.

예제 입력 1

3
blue3 blue5 blue6
4
blue4 yellow4 red4 black4

예제 출력 1

3

예제 입력 2

8
blue6 blue7 yellow3 yellow6 red3 red6 red7 black1 
9
blue2 blue4 yellow2 yellow4 red2 red4 black2 black3 black4 

예제 출력 2

5