매끄럽게 만들기

N개의 픽셀로 이루어진 일차원 배열이 있다. 각 픽셀은 0 이상 255 이하의 수로 표현되는 값을 가진다. 두 픽셀 사이의 거리는 두 수의 차이의 절댓값이다.

다음 각 연산을 영 번 이상 수행할 수 있다.

• 비용 D로 임의의 픽셀을 삭제하여, 원래 그 픽셀과 이웃하던 픽셀들이 서로 이웃하게 만들 수 있다.

• 비용 I로 임의의 값을 가진 픽셀 하나를 임의의 위치에 삽입할 수 있다. 두 기존 픽셀 사이, 첫 번째 픽셀 앞, 또는 마지막 픽셀 뒤에 삽입할 수 있다.

• 임의의 픽셀의 값을 바꿀 수 있다. 비용은 해당 픽셀의 이전 값과 새로운 값의 차이의 절댓값이다.

서로 이웃한 어떤 픽셀 사이의 거리도 최대 M이면 배열은 매끄럽다. 배열을 매끄럽게 만드는 일련의 연산에 드는 비용으로 가능한 최솟값을 구한다.

참고: 빈 배열, 즉 픽셀이 하나도 없는 배열도 매끄러운 것으로 간주한다.

제한

테스트 세트당 시간 제한: 30초. 메모리 제한: 1GB. 입력의 모든 수는 정수이다. 1 ≤ T ≤ 100 0 ≤ D, I, M, $a_{i}$ ≤ 255

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

1 ≤ N ≤ 3.

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

1 ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 각각 두 줄로 이루어진 T개의 테스트 케이스가 주어진다. 첫 번째 줄은 "D I M N" 형식이고, 다음 줄에는 왼쪽부터 오른쪽까지의 픽셀 값인 N개의 수 $a_{i}$가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 입력 배열을 매끄럽게 만드는 최소 비용이다.

설명

케이스 #1에서는 7을 3로 줄이는 데 4의 비용이 들며, 이것이 가장 저렴한 해법이다. 케이스 #2에서는 삭제 비용이 매우 크므로, 원소를 삽입하여 최종 배열을 [1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 50, 45, 40, 35, 30, 25, 20, 15, 10, 7]와 같은 모습으로 만드는 편이 더 저렴하다.