Make it Smooth (Large)

You have a one dimensional array of $N$ pixels. Each pixel holds an integer value between 0 and 255, inclusive. The distance between two pixels is the absolute difference of their values.

You may perform each of the following operations any number of times, including zero.

1. For a cost of $D$, delete one pixel. The two pixels that were its neighbors become neighbors of each other.
2. For a cost of $I$, insert one pixel with any value between 0 and 255 at any position: between two existing pixels, before the first pixel, or after the last pixel.
3. Change the value of one pixel. The cost is the absolute difference between the old value and the new value.

An array is smooth if every pair of neighboring pixels has distance at most $M$. Find the minimum total cost of a sequence of operations that makes the array smooth.

The empty array, the array with no pixels at all, counts as smooth.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains $D$, $I$, $M$, and $N$ separated by spaces. The second line contains the pixel values $a_1, a_2, \dots, a_N$ from left to right.

Limits

• Every number in the input is an integer.
• $1 \le T \le 100$
• $0 \le D, I, M, a_i \le 255$
• $1 \le N \le 100$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum cost of making that array smooth.

In the first sample case, lowering the 7 to a 3 costs 4 and is the cheapest option. In the second sample case, deleting is very expensive, so inserting pixels until the final array is [1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 50, 45, 40, 35, 30, 25, 20, 15, 10, 7] costs less.