여행 계획 (라지)

남극의 천문학자들이 아직 발표하지 않은 관측에 따르면, 우주에는 사람이 사는 행성이 $N$개 있고 모두 같은 직선 위에 놓여 있다. $i$번째 행성의 좌표는 $X_i$이다. 지구는 첫 번째 행성이고 좌표가 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 20$
• $2 \le N \le 30$
• $1 \le F \le 10^{17}$
• $-10^{15} \le X_i \le 10^{15}$
• $X_1 = 0$
• $X_i$는 모두 다르다.

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