부드럽게 만들기 (큰 입력)

길이가 $N$인 1차원 픽셀 배열이 있다. 각 픽셀은 0 이상 255 이하의 정수 값을 갖는다. 두 픽셀 사이의 거리는 두 값의 차의 절댓값이다.

다음 세 연산을 각각 원하는 만큼, 0번을 포함해 수행할 수 있다.

1. 비용 $D$를 내고 픽셀 하나를 삭제한다. 삭제된 픽셀의 양옆에 있던 픽셀은 서로 이웃이 된다.
2. 비용 $I$를 내고 0 이상 255 이하의 값을 갖는 픽셀 하나를 원하는 위치에 삽입한다. 기존 두 픽셀 사이, 맨 앞, 맨 뒤 어디든 넣을 수 있다.
3. 픽셀 하나의 값을 바꾼다. 비용은 바꾸기 전 값과 바꾼 뒤 값의 차의 절댓값이다.

이웃한 모든 픽셀 쌍의 거리가 $M$ 이하인 배열을 부드러운 배열이라고 한다. 주어진 배열을 부드럽게 만드는 연산 순서의 최소 비용을 구하라.

픽셀이 하나도 없는 빈 배열도 부드러운 배열로 본다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 각 테스트 케이스가 두 줄씩 주어진다. 첫 줄에는 $D$, $I$, $M$, $N$이 공백으로 구분되어 주어지고, 둘째 줄에는 왼쪽부터 순서대로 픽셀 값 $a_1, a_2, \dots, a_N$이 주어진다.

제한

• 입력의 모든 수는 정수다.
• $1 \le T \le 100$
• $0 \le D, I, M, a_i \le 255$
• $1 \le N \le 100$

각 테스트 케이스마다 한 줄에 Case #x: y 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그 배열을 부드럽게 만드는 최소 비용이다.

첫 번째 예제 케이스에서는 7을 3으로 낮추는 비용 4가 가장 싸다. 두 번째 예제 케이스에서는 삭제 비용이 매우 비싸므로, 픽셀을 삽입해 최종 배열을 [1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 50, 45, 40, 35, 30, 25, 20, 15, 10, 7]로 만드는 편이 더 싸다.