Bạn đang chơi một trò chơi với một bộ bài đặc biệt. Mỗi lá bài có ba chỉ số thưởng: thưởng rút bài c, thưởng điểm s, và thưởng lượt đi t. Một số lá bài bắt đầu trong tay bạn, trong khi những lá còn lại nằm trong một chồng bài trên bàn. Bạn bắt đầu với một lượt đi.

Trong mỗi lượt, bạn có thể chọn bất kỳ lá bài nào từ tay mình và đánh nó. Nếu lá bài đó có các chỉ số thưởng c, s, t, các điều sau sẽ xảy ra:

• Lá bài đó bị loại khỏi tay bạn và không bao giờ có thể sử dụng lại.
• Bạn rút c lá bài đầu tiên từ chồng bài vào tay mình. Nếu chồng bài có ít hơn c lá, bạn rút tất cả số bài còn lại.
• Tổng điểm của bạn tăng thêm s.
• Số lượt đi còn lại của bạn tăng thêm t.

Nếu bạn không còn lá bài nào trong tay khi bắt đầu một lượt, thì không có gì xảy ra trong lượt đó. Mục tiêu của bạn là đạt được số điểm cao nhất có thể trước khi hết lượt đi.

Ví dụ, giả sử tay và chồng bài của bạn chứa các lá bài sau:

         +---+---+---+            +---+---+---+
   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 |
         +---+---+---+            +---+---+---+

Bảng dưới đây cho thấy cách bạn có thể đạt được số điểm là 8 từ những lá bài này. Ba cột đầu tiên hiển thị bài trên tay, số lượt còn lại và số điểm của bạn trước khi đánh mỗi lá bài, và cột cuối cùng hiển thị lá bài được chọn để đánh.

+---------+------------+-------+------+
| 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   |   -  |
+---------+------------+-------+------+

Như bạn có thể thấy, các phần thưởng rút bài và phần thưởng lượt đi cho phép bạn tạo ra một chuỗi các lá bài liên tiếp trước khi phải dừng lại.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, T. T bộ thử nghiệm tiếp theo.

Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa N, số lượng lá bài trong tay bạn. N dòng tiếp theo, mỗi dòng chứa ba số nguyên c, s, và t, đại diện cho các chỉ số thưởng của một lá bài trong tay bạn.

Tiếp theo là một dòng chứa M, số lượng lá bài trong chồng bài. M dòng tiếp theo, mỗi dòng chứa ba số nguyên c, s, và t, đại diện cho các chỉ số thưởng của một lá bài trong chồng bài. Các lá bài này được liệt kê theo đúng thứ tự mà bạn sẽ rút chúng.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: S", trong đó S là số điểm lớn nhất bạn có thể đạt được trước khi hết lượt đi.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le N\).
• \(0 \le M\).
• \(N + M \le 80\).

Phân nhóm

• Test set 1 (Visible):

  • \(0 \le c \le 1\).
  • \(0 \le s \le 20\).
  • \(0 \le t \le 20\).

• Test set 2 (Hidden):

  • \(0 \le c \le 2\).
  • \(0 \le s \le 50\).
  • \(0 \le t \le 50\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
4
1 0 0
1 1 1
0 5 0
1 2 0
0
2
1 1 1
0 6 0
1
0 1 3

Case #1: 6
Case #2: 8

Nguồn

Google Code Jam 2011, Vòng 1A, bài Pseudominion.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.