부드럽게 만들기 (작은 입력)

픽셀 $N$개가 한 줄로 늘어선 배열이 있다. 각 픽셀의 값은 0 이상 255 이하의 정수다. 두 픽셀의 거리는 두 값의 차의 절댓값이다.

다음 세 연산을 각각 원하는 횟수만큼 수행할 수 있다. 한 번도 하지 않아도 된다.

1. 비용 $D$를 내고 픽셀 하나를 지운다. 지운 픽셀의 양옆에 있던 픽셀은 서로 이웃이 된다.
2. 비용 $I$를 내고 원하는 값의 픽셀 하나를 원하는 자리에 끼워 넣는다. 두 픽셀 사이, 맨 앞, 맨 뒤 어디든 가능하다.
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 3$

각 테스트 케이스마다 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]로 만드는 편이 더 싸다.