Pseudominion (라지)

특이한 카드로 하는 카드 게임을 한다. 카드마다 보너스 수가 세 개씩 적혀 있다. 카드 보너스 $c$, 점수 보너스 $s$, 턴 보너스 $t$이다. 일부 카드는 처음부터 손에 있고, 나머지는 탁자 위 덱에 쌓여 있다. 점수는 0에서 시작하고, 턴은 하나만 가지고 시작한다.

한 턴에 손에 있는 카드 중 하나를 골라서 낸다. 낸 카드의 보너스 수가 $c$, $s$, $t$이면 다음이 모두 일어난다.

• 낸 카드는 버려지고, 다시 쓸 수 없다.
• 덱의 맨 위 $c$장을 손으로 가져온다. 덱에 남은 카드가 $c$장보다 적으면 남은 카드를 모두 가져온다.
• 점수가 $s$만큼 오른다.
• 남은 턴 수가 $t$만큼 늘어난다.

카드를 내면 언제나 턴을 하나 쓰므로, $t = 0$인 카드를 내면 남은 턴이 하나 줄어든다. 턴이 시작될 때 손이 비어 있으면 그 턴에는 아무 일도 일어나지 않는다. 남은 턴이 없으면 게임이 끝난다. 얻을 수 있는 가장 큰 점수를 구하라.

예를 들어 카드 여섯 장이 아래와 같다고 하자. 덱은 4번, 5번, 6번 순서로 뽑는다.

1번, 3번, 2번, 5번, 4번 순서로 내면 점수 8을 얻는다. 아래 표의 각 행은 마지막 열에 적힌 카드를 내기 직전의 손, 남은 턴, 점수를 나타낸다.

카드 보너스와 턴 보너스 덕분에 멈추기 전까지 카드를 길게 이어서 낼 수 있다.

첫 줄에 테스트 케이스 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 손에 든 카드 수 $N$이 주어진다. 다음 $N$개 줄에는 손에 든 카드 한 장의 보너스 수 $c$, $s$, $t$가 주어진다. 그다음 줄에는 덱에 있는 카드 수 $M$이 주어지고, 다음 $M$개 줄에는 덱에 있는 카드 한 장의 보너스 수 $c$, $s$, $t$가 주어진다. 덱의 카드는 뽑는 순서대로 나열된다.

제한

• $1 \le T \le 100$
• $1 \le N$
• $0 \le M$
• $N + M \le 80$
• $0 \le c \le 2$
• $0 \le s \le 50$
• $0 \le t \le 50$

각 테스트 케이스마다 Case #x: S 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $S$는 턴이 다하기 전까지 얻을 수 있는 가장 큰 점수이다.