Pseudominion

화려한 카드 덱으로 게임을 하고 있다. 각 카드에는 카드 보너스 c, 점수 보너스 s, 턴 보너스 t라는 세 가지 보너스 수가 있다. 일부 카드는 처음부터 손에 있고, 나머지는 테이블 위의 덱에 있다. 한 턴을 가진 상태로 시작한다.

각 턴에는 손에 있는 카드 중 아무 카드나 선택해 사용할 수 있다. 그 카드의 보너스 수가 c, s, t라면 다음과 같은 일이 일어난다.

• 그 카드를 손에서 버리며, 다시는 사용할 수 없다.

• 덱의 맨 앞 c장을 뽑아 손에 넣는다. 덱에 c장보다 적은 카드가 있다면 모두 뽑는다.

• 총점이 s만큼 증가한다.

• 남은 턴 수가 t만큼 증가한다.

어떤 턴이 시작될 때 손에 카드가 하나도 없다면 그 턴에는 아무 일도 일어나지 않는다. 목표는 턴을 모두 소진하기 전에 가능한 한 높은 점수를 얻는 것이다.

예를 들어, 손과 덱에 다음 카드들이 있다고 하자.

+---+---+---+            +---+---+---+
   HAND: | c | s | t |      DECK: | c | s | t |
         +---+---+---+            +---+---+---+
Card #1: | 0 | 0 | 2 |   Card #4: | 1 | 1 | 0 |
Card #2: | 0 | 5 | 0 |   Card #5: | 0 | 1 | 1 |
Card #3: | 2 | 1 | 1 |   Card #6: | 2 | 2 | 0 |
         +---+---+---+            +---+---+---+

다음 표는 이 카드들로 8점을 얻는 방법을 보여 준다. 처음 세 열은 각 카드를 사용하기 전의 손, 남은 턴 수, 점수를 보여 주며, 마지막 열은 사용할 카드를 보여 준다.

+---------+------------+-------+------+
| Hand    | Turns left | Score | Play |
+---------+------------+-------+------+
| 1, 2, 3 |      1     |   0   |   1  |
| 2, 3    |      2     |   0   |   3  |
| 2, 4, 5 |      2     |   1   |   2  |
| 4, 5    |      1     |   6   |   5  |
| 4       |      1     |   7   |   4  |
| 6       |      0     |   8   |   -  |
+---------+------------+-------+------+

보다시피 카드 보너스와 턴 보너스를 이용하면 멈춰야 할 때가 오기 전에 긴 카드 사용 순서를 연이어 이어 갈 수 있다.

제한

1 ≤ T ≤ 100. 1 ≤ N. 0 ≤ M. N + M ≤ 80. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

0 ≤ c ≤ 1. 0 ≤ s ≤ 20. 0 ≤ t ≤ 20. 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

0 ≤ c ≤ 2. 0 ≤ s ≤ 50. 0 ≤ t ≤ 50. 시간 제한: 60초.

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

각 테스트 케이스는 손에 있는 카드의 수 N이 적힌 한 줄로 시작한다. 다음 N개의 줄에는 각각 손에 있는 카드 한 장의 보너스 수를 나타내는 세 정수 c, s, t가 주어진다.

그다음에는 덱에 있는 카드의 수 M이 적힌 한 줄이 주어진다. 다음 M개의 줄에는 각각 덱에 있는 카드 한 장의 보너스 수를 나타내는 세 정수 c, s, t가 주어진다. 이 카드들은 뽑게 되는 순서와 같은 순서로 나열된다.

각 테스트 케이스마다 "Case #x: S"를 포함하는 한 줄을 출력한다. 여기서 S는 턴을 모두 소진하기 전에 얻을 수 있는 가장 높은 점수이다.