Trong một khám phá mới của các nhà thiên văn học Nam Cực, người ta ghi lại rằng có \(N\) hành tinh có sự sống trong không gian, tất cả đều nằm trên cùng một đường thẳng. Hành tinh thứ \(i\) nằm ở tọa độ \(X_i\) trên đường thẳng đó (\(i = 1, 2, \dots, N\)). Trái Đất là hành tinh đầu tiên, nằm ở tọa độ \(0\), vì vậy \(X_1\) sẽ luôn bằng \(0\).

Rất hào hứng với sự thật này, bạn bắt đầu lập kế hoạch cho một chuyến đi để thăm tất cả các hành tinh. Vì các hành tinh lạ có thể nguy hiểm, bạn muốn ghé thăm mỗi hành tinh đúng một lần trước khi quay trở lại Trái Đất. Bạn có \(F\) đơn vị nhiên liệu và bạn muốn tiêu tốn càng nhiều nhiên liệu càng tốt cho chuyến đi này để lần hạ cánh cuối cùng xuống Trái Đất được an toàn hơn. Con tàu vũ trụ của bạn khá cơ bản và chỉ có thể bay theo một đường thẳng từ bất kỳ hành tinh \(i\) nào đến bất kỳ hành tinh \(j\) nào khác, tiêu tốn \(|X_i - X_j|\) đơn vị nhiên liệu trên đường đi. Nó không thể quay đầu mà không hạ cánh.

Vì vậy, bạn cần lập một kế hoạch du hành yêu cầu tối đa \(F\) đơn vị nhiên liệu, bắt đầu từ Trái Đất, ghé thăm mỗi hành tinh khác đúng một lần, và sau đó quay trở lại Trái Đất. Nếu có nhiều kế hoạch như vậy, bạn nên tìm kế hoạch tiêu tốn nhiều nhiên liệu nhất. Hãy xuất ra lượng nhiên liệu tiêu thụ đó.

Dữ liệu vào

Dòng đầu tiên của đầ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 số lượng hành tinh \(N\). Dòng tiếp theo chứa \(N\) số \(X_i\), tọa độ của các hành tinh. Dòng tiếp theo chứa lượng nhiên liệu \(F\) mà bạn có.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất ra một dòng chứa "Case #x: NO SOLUTION" nếu không có kế hoạch du hành nào như vậy, hoặc "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là lượng nhiên liệu tiêu thụ tối đa.

Ràng buộc

• \(1 \le F \le 10^{17}\).
• \(-10^{15} \le X_i \le 10^{15}\).
• \(X_1 = 0\).
• Tất cả các \(X_i\) đều khác nhau.

Phân nhóm

• Small dataset (Tập kiểm thử 1 - Hiển thị): \(1 \le T \le 100\); \(2 \le N \le 10\).
• Large dataset (Tập kiểm thử 2 - Ẩn): \(1 \le T \le 20\); \(2 \le N \le 30\).

Đ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
3
0 10 -10
40
5
0 1 2 3 4
13
5
0 1 2 3 4
7

Case #1: 40
Case #2: 12
Case #3: NO SOLUTION

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài Travel Plan.

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