만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

여행 계획

시간 제한5초메모리 제한512 MB

요약
지구에서 출발해 일직선 위의 모든 행성을 정확히 한 번씩 방문하고 지구로 돌아오는 경로 중 연료 F를 넘지 않으면서 가장 많은 연료를 쓰는 양을 구합니다.
난이도

보통10점 중 7점

유형
동적 계획법, 완전 탐색
정답자
아직 제출이 없습니다

문제

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

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

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

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다. 각 테스트 케이스의 첫 줄에는 행성의 수 NN이 주어진다. 다음 줄에는 행성의 좌표 X1,X2,…,XNX_1, X_2, \dots, X_N이 주어진다. 그다음 줄에는 가지고 있는 연료의 양 FF가 주어진다.

제한

  • 1≤T≤1001 \le T \le 100
  • 2≤N≤102 \le N \le 10
  • −1015≤Xi≤1015-10^{15} \le X_i \le 10^{15}
  • X1=0X_1 = 0
  • 모든 XiX_i는 서로 다르다.
  • 1≤F≤10171 \le F \le 10^{17}

출력

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

예제2

  1. 예제 1

    입력
    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

  2. 예제 2

    입력
    3
2
0 1
1
2
0 1
2
2
0 -1000000000000000
100000000000000000
    예상 출력
    Case #1: NO SOLUTION
Case #2: 2
Case #3: 2000000000000000