You have a one-dimensional array of N pixels. Each pixel has a value, represented by a number between 0 and 255, inclusive. The distance between two pixels is the absolute difference of their numbers.
You can perform each of the following operations zero or more times:
The array is smooth if any neighboring pixels have distance at most M. Find the minimum possible cost of a sequence of operations that makes the array smooth.
Note: The empty array -- the array containing no pixels -- is considered to be smooth.
The first line of the input gives the number of test cases, T. T test cases follow, each with two lines. The first line is in the form "D I M N", the next line contains N numbers ai: the values of the pixels from left to the right.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the minimum cost to make the input array smooth.
All the numbers in the input are integers.
1 ≤ T ≤ 100
0 ≤ D, I, M, ai ≤ 255
1 ≤ N ≤ 3.
1 ≤ N ≤ 100.
In Case #1, decreasing the 7 to 3 costs 4 and is the cheapest solution.
In Case #2, deleting is extremely expensive; it's cheaper to insert
elements so your final array looks like
[1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 50, 45, 40, 35, 30, 25, 20, 15, 10, 7].