Description

你有一个长度为 $N$ 的一维像素数组。每个像素都有一个取值，表示为 $0$ 到 $255$ 之间的一个数字（包含 $0$ 和 $255$）。两个像素之间的距离定义为它们数值的绝对差。

你可以进行以下任意次数的操作：

1. 以代价 $D$，删除任意一个像素，此时它原本的相邻像素会变为新的相邻像素。
2. 以代价 $I$，在任意位置插入一个任意值的像素——可以插在任意两个像素之间，也可以插在第一个像素之前或最后一个像素之后。
3. 你可以修改任意一个像素的值，代价为该像素的新旧值的绝对差。

如果数组中任意相邻像素的距离都不超过 $M$，则称该数组是“平滑”的。请你求出将输入数组变为平滑数组所需的最小总代价。

注意：空数组（即不包含任何像素的数组）也被认为是平滑的。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据，每组包含两行。第一行为 "D I M N"，下一行为 $N$ 个数字 $a_i$，表示从左到右的像素值。

Output Format

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 为测试编号（从 1 开始），$y$ 为使输入数组变为平滑数组的最小总代价。

2
6 6 2 3
1 7 5
100 1 5 3
1 50 7

Case #1: 4
Case #2: 17

Hint

样例解释

在第 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]$ 更便宜。

数据范围

• 输入中的所有数字均为整数。
• $1 \leqslant T \leqslant 100$
• $0 \leqslant D, I, M, a_i \leqslant 255$

小数据范围（12 分，测试点 1 - 可见）

• $1 \leqslant N \leqslant 3$。

大数据范围（24 分，测试点 2 - 隐藏）

• $1 \leqslant N \leqslant 100$。

由 ChatGPT 4.1 翻译