여행 계획

남극의 천문학자들이 아직 공개하지 않은 관측 기록에 따르면, 우주에는 사람이 사는 행성이 $N$개 있고 모두 같은 직선 위에 놓여 있다. $i$번째 행성은 그 직선의 좌표 $X_i$에 있다. 지구는 1번째 행성이고 좌표가 0이므로 $X_1 = 0$이다.

이 사실에 들뜬 당신은 모든 행성을 도는 여행을 계획한다. 알려지지 않은 행성은 위험하니 각 행성을 정확히 한 번씩만 방문하고 지구로 돌아온다. 연료는 $F$만큼 있고, 지구에 착륙할 때 남은 연료가 적을수록 착륙이 안전하므로 이번 여행에서 연료를 최대한 많이 쓰려 한다. 우주선은 성능이 낮아서 행성 $i$에서 다른 행성 $j$로 직선으로만 날 수 있고 그동안 연료를 $|X_i - X_j|$만큼 쓴다. 착륙하지 않으면 방향을 바꾸지 못한다.

지구에서 출발해 나머지 행성을 각각 정확히 한 번씩 방문하고 지구로 돌아오면서 연료를 $F$ 이하로 쓰는 여행 계획을 세워야 한다. 그런 계획이 여럿이면 연료를 가장 많이 쓰는 계획을 고른다. 소모한 연료의 양을 출력한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 행성의 수 $N$이 주어진다. 다음 줄에는 행성의 좌표 $X_1, X_2, \dots, X_N$이 주어진다. 그다음 줄에는 가지고 있는 연료의 양 $F$가 주어진다.

제한

• $1 \le T \le 100$
• $2 \le N \le 10$
• $-10^{15} \le X_i \le 10^{15}$
• $X_1 = 0$
• 모든 $X_i$는 서로 다르다.
• $1 \le F \le 10^{17}$

각 테스트 케이스마다 한 줄을 출력한다. 조건을 만족하는 여행 계획이 없으면 Case #x: NO SOLUTION을, 있으면 Case #x: y를 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 소모할 수 있는 연료의 최댓값이다.