여행 계획

남극의 천문학자들이 아직 발표하지 않았고 재검토 중인 발견에 따르면, 우주에는 사람이 거주하는 N개의 행성이 있으며 모두 같은 직선 위에 놓여 있고, i번째 행성은 직선 (i = 1, 2, ..., N) 위의 좌표 $X_{i}$에 있다고 한다. 지구는 좌표 영에 있는 첫 번째 행성이므로, $X_{1}$는 항상 0와 같다.

이 사실에 매우 들뜬 당신은 모든 행성을 방문하는 여행을 계획하기 시작한다. 미지의 행성은 위험할 수 있으므로, 지구로 돌아오기 전에 각 행성을 정확히 한 번씩 방문하려 한다. 연료는 F단위가 있으며, 지구에 마지막으로 착륙할 때 더 안전하도록 이 여행에서 가능한 한 많은 연료를 사용하려 한다. 우주선은 매우 기본적인 기능만 갖추고 있어 임의의 행성 i에서 다른 임의의 행성 j까지 직선을 따라 비행할 수만 있으며, 이동하는 동안 |$X_{i}$-$X_{j}$|단위의 연료를 소비한다. 착륙하지 않고는 방향을 바꿀 수 없다.

따라서 최대 F단위의 연료가 필요하고, 지구에서 출발하여 나머지 각 행성을 정확히 한 번씩 방문한 다음 지구로 돌아오는 여행 계획을 세워야 한다. 그러한 계획이 여러 개라면 연료를 가장 많이 소비하는 계획을 찾아야 한다. 소비되는 연료의 양을 출력한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ F ≤ $10^{17}$. -$10^{15}$ ≤ $X_{i}$ ≤ $10^{15}$. $X_{1}$=0. 모든 $X_{i}$는 서로 다르다.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 100. 2 ≤ N ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 20. 2 ≤ N ≤ 30.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 설명은 행성의 수 N이 주어지는 줄로 시작한다. 다음 줄에는 행성의 좌표인 N개의 수 $X_{i}$가 주어진다. 그다음 줄에는 가지고 있는 연료의 양 F가 주어진다.

각 테스트 케이스마다 그러한 여행 계획이 없으면 "Case #x: NO SOLUTION"를 포함하는 한 줄을 출력하고, 그렇지 않으면 "Case #x: y"를 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고 y는 소비되는 연료의 최대량이다.