햇살 섬

어느 날 태평양 한가운데에서 화산이 폭발했다. 용암이 식은 뒤, 작은 해님 모양의 새로운 섬이 나타났다. 물 위로 솟은 땅은 원(분화구) 모양이었고, 흘러나와 굳은 용암은 원 바깥으로 뻗어 나가는 곧은 광선들을 이루었다.

곧 관광객이 몰려들었고 노점이 세워졌다. 노점은 세 종류의 자리에 놓인다.

• 분화구 둘레에는 시계 방향으로 $1$번부터 $n$번까지 노점이 놓인다. 번호가 이웃한 노점끼리는 서로 인접하며, $n$번 노점은 $1$번 노점과 인접한다. 즉 둘레의 노점들은 하나의 고리를 이룬다.
• 분화구 위에는 다리가 놓이며, 각 다리는 둘레의 두 노점에 걸쳐 있다. 어떤 두 다리도 서로 교차하거나 겹쳐 놓이지 않는다. 한 다리로 연결된 두 노점은 서로 인접하다.
• 굳은 용암의 광선은 일부 둘레 노점에서 바깥으로 뻗는다. 광선 위의 노점들은 사슬을 이룬다. 광선의 첫 노점은 그 광선이 시작되는 둘레 노점과 인접하고, 그다음 노점들은 각각 바로 앞 노점과 인접한다.

섬의 법은 인접한 두 노점이 단 하나의 상품도 공유하지 못하도록 금지한다. 따라서 인접한 노점끼리는 완전히 다른 상품을 팔아야 한다. 각 노점은 장사를 이어 가기 위해 정해진 개수 이상의 서로 다른 상품을 팔아야 한다(다리 위에는 노점을 둘 수 없다).

모든 노점이 필요한 개수 이상의 상품을 배정받으면서도 인접한 두 노점이 어떤 상품도 공유하지 않도록 하려면, 섬에 들여와야 하는 서로 다른 상품의 최소 개수는 얼마인지 구하여라.

첫 줄에 데이터 집합의 수 $D$ ($1 \le D \le 20$)가 주어진다. 각 데이터 집합은 다음과 같이 주어진다.

첫 줄에 분화구 둘레의 노점 수 $n$ ($3 \le n \le 10000$)이 주어진다. 노점은 시계 방향으로 $1$번부터 $n$번까지 번호가 매겨진다.

다음 줄에 다리의 수 $m$ ($0 \le m \le n-3$)이 주어진다. 이어지는 $m$개의 줄에는 각각 두 정수 $p_i$, $k_i$ ($1 \le p_i < k_i \le n$, $p_i < k_i - 1$, $k_i - p_i \ne n-1$)가 주어지며, 한 다리의 양 끝에 있는 둘레 노점의 번호를 뜻한다.

다음 줄에 광선의 수 $r$ ($0 \le r \le n$)이 주어진다. 이어지는 $r$개의 줄에는 각각 두 정수 $c_j$, $d_j$ ($1 \le c_j \le n$, $0 \le d_j \le 10000$)가 주어지며, $j$번째 광선이 시작되는 둘레 노점의 번호와 그 광선 위에 있는 추가 노점의 수를 뜻한다.

다음 줄에는 $n$개의 정수가 주어지며, $i$번째 수는 $i$번 둘레 노점이 팔아야 하는 서로 다른 상품의 개수이다.

마지막으로 $r$개의 줄이 주어진다. $j$번째 줄에는 $d_j$개의 정수가 있으며, $j$번째 광선 위 노점들이 팔아야 하는 상품 개수를 분화구에 가까운 노점부터 먼 노점 순서로 나열한 것이다.

노점은 모두 합쳐 $100000$개를 넘지 않으며, 어떤 노점도 $100$개를 넘는 상품을 요구하지 않는다.

각 데이터 집합마다 한 줄에, 모든 노점이 필요한 개수 이상의 상품을 받고 인접한(또는 다리로 연결된) 두 노점이 어떤 상품도 공유하지 않도록 섬에 들여와야 하는 서로 다른 상품의 최소 개수 $t$를 출력한다.

그림 1. 예제에서 설명하는 섬의 지도.