Pseudominion (작은 입력)

카드 게임을 한다. 카드마다 보너스 수가 세 개 적혀 있다. 카드 보너스 $c$, 점수 보너스 $s$, 턴 보너스 $t$다. 처음에 몇 장은 손에 있고 나머지는 탁자 위의 덱에 쌓여 있다. 시작할 때 남은 턴 수는 1이고 점수는 0이다.

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

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

카드를 한 장 내면 남은 턴 수는 먼저 1 줄어들고, 그다음 $t$만큼 늘어난다. 턴을 시작할 때 손에 카드가 없으면 그 턴에는 아무 일도 일어나지 않는다. 남은 턴 수가 0이 되면 더 이상 카드를 낼 수 없다. 턴이 다 떨어지기 전에 얻을 수 있는 점수의 최댓값을 구한다.

다음 설명은 규칙이 어떻게 맞물리는지 보여주려고 붙인 것이며, 아래 제한보다 큰 $c$ 값을 포함한다.

아래 표는 이 카드로 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 1$
• $0 \le s \le 20$
• $0 \le t \le 20$

각 테스트 케이스마다 한 줄에 Case #x: S를 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $S$는 턴이 다 떨어지기 전에 얻을 수 있는 최대 점수다.