Có một tình huống khẩn cấp trong không gian! Bạn cần điều động soái hạm của hạm đội đi từ ngôi sao \(0\) đến ngôi sao \(N\) càng nhanh càng tốt, đi qua các ngôi sao khác theo thứ tự số tăng dần (\(0 \to 1 \to \dots \to N\)). Soái hạm của bạn bình thường di chuyển với tốc độ \(0,5\) parsec mỗi giờ.

Ngoài việc điều động soái hạm, bạn có thể ra lệnh cho các kỹ sư xây dựng tối đa \(L\) trạm tăng tốc tại các ngôi sao khác nhau. Việc xây dựng một trạm tăng tốc mất \(t\) giờ và tất cả \(L\) trạm tăng tốc có thể được xây dựng song song. Trong khi soái hạm di chuyển từ một ngôi sao đã hoàn thành trạm tăng tốc đến ngôi sao tiếp theo, tốc độ của nó là \(1\) parsec mỗi giờ.

Nếu một trạm tăng tốc được hoàn thành tại một ngôi sao trong khi soái hạm đang di chuyển từ ngôi sao đó đến ngôi sao tiếp theo, soái hạm sẽ bắt đầu di chuyển nhanh hơn ngay khi trạm tăng tốc được hoàn thành.

Hỏi mất bao nhiêu giờ để soái hạm của bạn đến được ngôi sao \(N\) nếu bạn xây dựng các trạm tăng tốc để nó đến nơi sớm nhất có thể?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa các số nguyên \(L, t, N\) và \(C\), theo sau là \(C\) số nguyên \(a_i\), tất cả cách nhau bởi dấu cách. \(a_i\) là số parsec giữa ngôi sao \(k \times C + i\) và ngôi sao \(k \times C + i + 1\), với mọi giá trị nguyên của \(k\).

Ví dụ, với \(N=8, C=3, a_0=3, a_1=5\) và \(a_2=4\), khoảng cách giữa các ngôi sao là \([3, 5, 4, 3, 5, 4, 3, 5]\).

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là một số nguyên duy nhất: số giờ cần thiết để đến được ngôi sao \(N\). Đáp án được đảm bảo luôn là một số nguyên.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le C \le 1000\).
• \(C \le N\).
• \(1 \le a_i \le 10^4\).
• \(0 \le t \le 10^{11}\).
• \(t\) là số chẵn.

Phân nhóm

• Small dataset (Test set 1): \(1 \le N \le 1000\); \(0 \le L \le 2\).
• Large dataset (Test set 2): \(1 \le N \le 10^6\); \(0 \le L \le N\).

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

Case #1: 54
Case #2: 20

Lưu ý: Bài toán này diễn ra trong một vũ trụ nơi tốc độ ánh sáng cao hơn nhiều so với 1 parsec mỗi giờ, vì vậy chúng ta không cần lo lắng về các hiệu ứng thuyết tương đối hẹp.

Nguồn

Google Code Jam 2011, Vòng 1C, bài Space Emergency.

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