칩 카드

Johnny는 칩 카드용 칩을 설계한다. 칩의 위쪽 경계와 아래쪽 경계에는 각각 $n$개의 포트가 있다. 위쪽 포트는 왼쪽에서 오른쪽으로 $1, 2, \ldots, n$ 번호가 붙어 있다. 아래쪽 포트에도 같은 번호가 왼쪽에서 오른쪽으로 붙어 있지만, 순서는 다를 수 있다. 같은 번호를 가진 포트 쌍은 직선 경로로 연결된다. 경로는 층으로 묶이며, 같은 층의 경로끼리는 교차할 수 없다.

각 경계의 포트는 소켓으로 묶여 있다. 각 소켓은 연속된 포트로 이루어지고, 모든 포트는 정확히 하나의 소켓에 속한다. 아래쪽 소켓의 길이는 위쪽 소켓의 길이와 다를 수 있다. 소켓은 뒤집을 수 있으며, 뒤집으면 그 안에 있는 포트의 순서가 반대가 된다.

Johnny는 곧 해고된다는 소식을 들었다. 그는 작은 복수를 하려고 다음 칩의 제작 비용이 최대가 되도록 설계하려 한다. 제작 비용의 핵심은 필요한 층의 수이므로, 그는 필요한 층의 수가 최대가 되도록 각 소켓을 뒤집는다. 이 문제는 그의 평소 업무보다 훨씬 어려워서 Johnny는 당신의 도움이 필요하다.

첫 줄에는 각 경계의 포트 수 $n$ ($1 \le n \le 5000$)이 주어진다. 둘째 줄에는 $\{1, 2, \ldots, n\}$에서 고른 서로 다른 정수 $n$개가 아래쪽 포트의 번호를 순서대로 주어진다. 셋째 줄에는 위쪽 소켓의 개수 $k$ ($1 \le k \le n$)와, 이어서 연속된 위쪽 소켓들의 포트 수 $k$개가 주어진다. 각 소켓은 최소 하나의 포트를 가지며, 위쪽 소켓들의 포트 수 합은 $n$이다. 넷째 줄에는 아래쪽 소켓에 대한 정보가 같은 형식으로 주어진다.

필요한 층의 최대 개수를 나타내는 양의 정수 하나를 출력한다.

위쪽 첫 번째 소켓은 포트 $1, 2, 3$을, 두 번째 소켓은 포트 $4$를, 세 번째 소켓은 포트 $5, 6, 7, 8$을 포함한다. 소켓을 뒤집으면 위쪽 경계의 포트를 다음 순서들로 만들 수 있다.

• $(1, 2, 3)$ $(4)$ $(5, 6, 7, 8)$
• $(1, 2, 3)$ $(4)$ $(8, 7, 6, 5)$
• $(3, 2, 1)$ $(4)$ $(5, 6, 7, 8)$
• $(3, 2, 1)$ $(4)$ $(8, 7, 6, 5)$