Sau bốn năm, mùa World Cup lại đến và Varva đang trên đường tới Nam Phi, vừa kịp lúc để theo dõi giai đoạn thứ hai của giải đấu.

Trong giai đoạn thứ hai (còn gọi là giai đoạn loại trực tiếp), mỗi trận đấu luôn có một đội thắng; đội thắng sẽ tiến vào vòng tiếp theo trong khi đội thua bị loại khỏi giải đấu. Có \(2^P\) đội tham gia ở giai đoạn này, được đánh số bằng các số nguyên từ \(0\) đến \(2^P - 1\). Giai đoạn loại trực tiếp gồm \(P\) vòng. Trong mỗi vòng, mỗi đội còn lại chơi đúng một trận. Các cặp đấu và thứ tự các trận đấu được xác định bằng cách chọn liên tiếp hai đội còn lại có số hiệu thấp nhất và ghép họ vào một trận đấu. Sau khi tất cả các trận đấu trong một vòng kết thúc, vòng tiếp theo sẽ bắt đầu.

Để giúp mình quyết định xem nên xem trận đấu nào, Varva đã lập một danh sách các ràng buộc dựa trên mức độ yêu thích của mình đối với từng đội cụ thể. Cụ thể, đối với mỗi đội \(i\), anh ấy sẵn lòng bỏ lỡ tối đa \(M[i]\) trận đấu mà đội đó thi đấu trong giải.

Varva cần mua một bộ vé để đảm bảo rằng các sở thích của mình được thỏa mãn, bất kể kết quả các trận đấu diễn ra như thế nào. Ngoài ra, anh ấy chỉ muốn chi ít tiền nhất có thể. Mục tiêu của bạn là tìm số tiền tối thiểu anh ấy cần chi để mua vé.

Vé cho các trận đấu cần được mua trước (trước khi giải đấu bắt đầu) và giá vé cho mỗi trận đấu đã được biết trước. Lưu ý rằng, trong dữ liệu nhỏ (small input), giá vé cho tất cả các trận đấu sẽ bằng nhau, trong khi ở dữ liệu lớn (large input), chúng có thể khác nhau.

Ví dụ

Một lịch trình giải đấu mẫu cùng với giá vé được đưa ra trong hình trên. Giả sử các ràng buộc được cho bởi mảng \(M = \{1, 2, 3, 2, 1, 0, 1, 3\}\), chiến lược tối ưu như sau: Vì chúng ta không thể bỏ lỡ bất kỳ trận đấu nào của đội 5, chúng ta sẽ cần chi \(50, 400\) và \(800\) để mua vé cho tất cả các trận đấu mà đội 5 có thể tham gia. Bây giờ, các ràng buộc cho các đội khác cũng được thỏa mãn bởi các vé này, ngoại trừ đội 0. Lựa chọn tốt nhất để khắc phục điều này là mua vé cho trận đấu vòng đầu tiên của đội 0, chi thêm \(100\), nâng tổng số tiền lên \(1350\).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên duy nhất \(P\). Dòng tiếp theo chứa \(2^P\) số nguyên -- các ràng buộc \(M[0], \dots, M[2^P-1]\).

Khối \(P\) dòng tiếp theo chứa giá vé cho tất cả các trận đấu: dòng đầu tiên của khối chứa \(2^{P-1}\) số nguyên -- giá vé cho các trận đấu vòng đầu tiên, dòng thứ hai của khối chứa \(2^{P-2}\) số nguyên -- giá vé cho các trận đấu vòng thứ hai, v.v. Dòng cuối cùng trong \(P\) dòng chứa một số nguyên duy nhất -- giá vé cho trận chung kết World Cup. Các mức giá được liệt kê theo thứ tự các trận đấu được diễn ra.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số tiền tối thiểu Varva cần chi cho vé như mô tả ở trên.

Ràng buộc

• \(1 \le T \le 50\).
• \(1 \le P \le 10\).
• Mỗi phần tử của \(M\) là một số nguyên từ \(0\) đến \(P\), bao gồm cả hai đầu.

Phân nhóm

• Dữ liệu nhỏ (Test set 1 - Visible): Tất cả giá vé đều bằng 1.
• Dữ liệu lớn (Test set 2 - Hidden): Tất cả giá vé là các số nguyên từ \(0\) đến \(100000\), bao gồm cả hai đầu.

Đ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
2
1 1 0 1
1 1
1
3
1 2 3 2 1 0 1 3
100 150 50 90
500 400
800

Case #1: 2
Case #2: 1350

Nguồn

Google Code Jam 2010, Vòng 2, bài World Cup 2010.

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