오벨릭스

오벨릭스는 대식가다. 오벨릭스가 대식가라는 사실은 학생회 회장까지 아는 모두가 아는 사실이다. 그는 매일 멧돼지를 먹는다. 하지만 그가 미식가이기도 하다는 사실을 아는 사람은 거의 없다. 오벨릭스는 같은 조리법으로 두 번 요리하는 법이 없다. 언젠가 시도해 보고 싶은 모든 조리법을 오래된 책에 모아 둔다. 조리법마다 그 요리를 만들기 위해 필요한 재료 목록이 있다. 그는 요리의 맛이 어떨지 생각하는 대로 각 조리법에 등급을 매겨 두기까지 했다. 부엌 식료품 저장고에는 필요한 모든 재료가 무한히 있다. 유일한 문제는 재료가 결국 신선함을 잃고 상한다는 것이다. 한 재료에 속한 모든 물품은 유통기한이 같기 때문이다.

오벨릭스는 앞으로 매일 다른 요리를 만들어, 상한 재료를 쓰지 않으면서 만든 모든 요리의 등급 합을 최대로 하고 싶어 한다. 아스테릭스는 매일 그의 손님이 될 만큼 운이 좋지만, 어떤 요리를 만들지 고르는 일은 둘 다 어려워할 것이다. 도와줄 수 있겠는가?

입력은 여러 테스트 케이스로 이루어진다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수가 하나 주어진다. 각 테스트 케이스의 첫 줄에는 공백 하나로 구분된 세 정수 $n$ ($1\le n \le 100000$), $i$ ($1\le i \le 100000$), $r$ ($1\le r \le 100000$)이 주어진다. $n$은 오벨릭스가 요리할 날의 수(날은 1부터 $n$까지 번호가 매겨진다)이고, $i$는 재료의 수(1부터 $i$까지 번호가 매겨진다)이며, $r$은 책에 있는 조리법의 수이다. 둘째 줄에는 공백 하나로 구분된 $i$개의 정수가 주어진다. $1 \leq j \leq i$에 대해 $j$번째 정수 $1 \leq e\_j \leq 100000$은 그 재료가 상하는 날, 즉 사용할 수 있는 마지막 날을 나타낸다. 그다음 $r$개의 줄이 각 조리법에 대해 하나씩 주어진다. $1 \leq k \leq r$에 대해 이 줄들 중 $k$번째 줄은 공백 하나로 구분된 정수들로 이루어진다. 첫 정수 $1 \leq g\_k \leq 100$은 조리법의 등급이고, 둘째 정수 $1 \leq l\_k \leq 10$은 조리법의 재료 수이며, 그다음에 $l\_k$개의 서로 다른 정수가 필요한 재료를 나타내는데, 각각 1과 $i$ 사이이다.

각 테스트 케이스에 대해, 각 조리법을 많아야 한 번 만들 수 있고 재료 중 하나가 유통기한이 지난 날에는 그 조리법을 만들 수 없다는 조건 아래에서, 오벨릭스가 $n$일 동안 만들 수 있는 조리법 등급 합의 최댓값을 출력한다.