Tàu lượn siêu tốc thật là vui! Có vẻ như tất cả những ai đến công viên giải trí đều muốn đi tàu lượn siêu tốc. Một số người đi một mình; những người khác đi theo nhóm và không muốn lên tàu trừ khi tất cả họ có thể đi cùng nhau. Và tất cả mọi người đã đi tàu lượn đều muốn đi thêm lần nữa. Một lượt đi tốn 1 Euro mỗi người; nhiệm vụ của bạn là tính xem tàu lượn siêu tốc sẽ kiếm được bao nhiêu tiền trong ngày hôm nay.

Tàu lượn có thể chứa tối đa \(k\) người cùng một lúc. Mọi người xếp hàng chờ theo từng nhóm. Các nhóm lần lượt lên tàu, từng nhóm một, cho đến khi không còn nhóm nào trong hàng hoặc không còn đủ chỗ cho nhóm tiếp theo; sau đó tàu sẽ chạy, dù có đầy chỗ hay không. Sau khi lượt đi kết thúc, tất cả hành khách trên lượt đó sẽ quay lại xếp hàng ở cuối hàng theo đúng thứ tự cũ. Tàu lượn sẽ chạy \(R\) lần trong một ngày.

Ví dụ, giả sử \(R=4\), \(k=6\), và có bốn nhóm người với kích thước: 1, 4, 2, 1.

• Lần chạy thứ nhất, hai nhóm đầu tiên [1, 4] sẽ đi, còn trống một chỗ (nhóm 2 người không vừa, và nhóm 1 người phía sau không thể đi trước họ). Sau đó họ quay lại cuối hàng, hàng đợi bây giờ là: 2, 1, 1, 4.
• Lần chạy thứ hai, tàu sẽ chở 4 người: [2, 1, 1]. Hàng đợi bây giờ là: 4, 2, 1, 1.
• Lần chạy thứ ba, tàu sẽ chở 6 người: [4, 2]. Hàng đợi bây giờ là: 1, 1, 4, 2.
• Lần chạy cuối cùng, tàu sẽ chở 6 người: [1, 1, 4].
  Tổng cộng tàu lượn đã kiếm được 21 Euro!

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\). Tiếp theo là \(T\) bộ test, mỗi bộ test gồm hai dòng.

• Dòng đầu tiên chứa ba số nguyên cách nhau bởi dấu cách: \(R\), \(k\) và \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(g_i\) cách nhau bởi dấu cách, mỗi số là kích thước của một nhóm muốn đi tàu. \(g_0\) là kích thước của nhóm đầu tiên, \(g_1\) là kích thước của nhóm thứ hai, v.v.

Dữ liệu ra

Với mỗi bộ test, hãy xuất ra 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ố Euro mà tàu lượn kiếm được.

Ràng buộc

• \(1 \le T \le 50\).
• \(g_i \le k\).

Phân nhóm

• Small dataset (Test set 1):
  • \(1 \le R \le 1000\).
  • \(1 \le k \le 100\).
  • \(1 \le N \le 10\).
  • \(1 \le g_i \le 10\).
• Large dataset (Test set 2):
  • \(1 \le R \le 10^8\).
  • \(1 \le k \le 10^9\).
  • \(1 \le N \le 1000\).
  • \(1 \le g_i \le 10^7\).

Đ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ụ

3
4 6 4
1 4 2 1
100 10 1
1
5 5 10
2 4 2 3 4 2 1 2 1 3

Case #1: 21
Case #2: 100
Case #3: 20

Nguồn

Google Code Jam 2010, Vòng loại, bài Theme Park.

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