Edythe là một nữ phù thủy trẻ làm trong bộ phận đảm bảo chất lượng của Merlin, Inc., một nhà máy sản xuất phép thuật. Công việc của cô là kiểm thử các phép thuật do chính Merlin phát minh. Mỗi phép cần lượng chính xác của một số nguyên liệu và biến chúng thành những lượng khác của các nguyên liệu khác. Edythe phải thi triển mỗi phép đúng một lần để xác minh rằng nó hoạt động chính xác.

Cô chỉ có thể thi triển một phép nếu có đủ lượng cần thiết của từng nguyên liệu. Nếu những phép trước đã tạo ra đúng loại nguyên liệu, Edythe bắt buộc phải dùng chúng trước. Nếu vẫn thiếu, cô được phép lấy phần còn thiếu từ kho của Merlin. Ban đầu cô không có nguyên liệu nào; cuối cùng, cô được giữ toàn bộ nguyên liệu dư đã tạo ra mà chưa dùng.

Edythe muốn kiếm càng nhiều lợi nhuận càng tốt trong thời gian học việc. Cô phải thi triển đúng một lần mỗi phép trong \(N\) phép đã cho, nhưng được chọn thứ tự tùy ý. Giả sử mọi phép hoạt động như mong đợi, thứ tự nào giúp cô có tổng giá trị lớn nhất ở cuối?

Ví dụ, kế hoạch kiểm thử có ba phép:

1. Đầu vào: vàng trị giá 7 đô-la. Đầu ra: lưu huỳnh trị giá 5 đô-la.
2. Đầu vào: không có. Đầu ra: vàng trị giá 10 đô-la và lưu huỳnh trị giá 10 đô-la.
3. Đầu vào: vàng trị giá 3 đô-la và lưu huỳnh trị giá 20 đô-la. Đầu ra: cóc trị giá 2 đô-la.

Phép thứ nhất biến vàng thành lưu huỳnh, phép thứ hai triệu hồi vàng và lưu huỳnh từ hư không, còn phép thứ ba biến vàng và lưu huỳnh thành cóc.

Nếu thi triển theo thứ tự 1, 2, 3, trước hết Edythe lấy vàng trị giá 7 đô-la từ kho cho phép #1. Sau hai phép đầu, cô có vàng trị giá 10 đô-la và lưu huỳnh trị giá 15 đô-la. Phép cuối cần vàng trị giá 3 đô-la và lưu huỳnh trị giá 20 đô-la, nên cô phải dùng toàn bộ lưu huỳnh đã tạo, vàng trị giá 3 đô-la và lấy thêm lưu huỳnh trị giá 5 đô-la từ kho. Cuối cùng cô còn nguyên liệu trị giá 9 đô-la: 7 đô-la vàng và 2 đô-la cóc.

Nhưng có kế hoạch tốt hơn. Nếu thi triển theo thứ tự 3, 1, 2, cuối cùng cô có nguyên liệu trị giá 27 đô-la: 10 đô-la vàng, 15 đô-la lưu huỳnh và 2 đô-la cóc.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(N,M\), sau đó \(N\) dòng, mỗi dòng \(M\) số mô tả phép.

Dữ liệu ra

In Case #x: y, giá trị nguyên liệu cuối lớn nhất.

Ràng buộc

• \(1\le T\le100\), \(1\le N\le100\), mỗi số trong \([-100,100]\).

Phân nhóm

• Nhỏ: \(1\le M\le2\).
• Lớn: \(1\le M\le8\).

Đ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
3 1
1
0
-1
3 3
-7 5 0
10 10 0
3 -20 2

Case #1: 1
Case #2: 27

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Merlin QA.

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