Bạn có một mảng một chiều gồm \(N\) điểm ảnh (pixel). Mỗi điểm ảnh có một giá trị, được biểu diễn bằng một số nguyên từ \(0\) đến \(255\). Khoảng cách giữa hai điểm ảnh là giá trị tuyệt đối của hiệu giữa hai giá trị của chúng.

Bạn có thể thực hiện mỗi thao tác sau đây không giới hạn số lần:

1. Với chi phí \(D\), xóa bất kỳ điểm ảnh nào, khi đó các điểm ảnh lân cận ban đầu của nó sẽ trở thành lân cận của nhau.
2. Với chi phí \(I\), chèn một điểm ảnh có giá trị bất kỳ vào bất kỳ vị trí nào — giữa hai điểm ảnh hiện có, trước điểm ảnh đầu tiên, hoặc sau điểm ảnh cuối cùng.
3. Bạn có thể thay đổi giá trị của bất kỳ điểm ảnh nào. Chi phí là giá trị tuyệt đối của hiệu giữa giá trị cũ và giá trị mới của điểm ảnh đó.

Mảng được gọi là mượt (smooth) nếu bất kỳ hai điểm ảnh lân cận nào cũng có khoảng cách tối đa là \(M\). Hãy tìm chi phí tối thiểu để thực hiện một chuỗi các thao tác làm cho mảng trở nên mượt.

Lưu ý: Mảng rỗng — mảng không chứa điểm ảnh nào — được coi là mượt.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau, mỗi bộ gồm hai dòng. Dòng đầu tiên có dạng "\(D\) \(I\) \(M\) \(N\)", dòng tiếp theo chứa \(N\) số \(a_i\): giá trị của các điểm ảnh từ trái sang phải.

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là chi phí tối thiểu để làm cho mảng đầu vào trở nên mượt.

Ràng buộc

• Tất cả các số trong dữ liệu vào là số nguyên.
• \(1 \le T \le 100\)
• \(0 \le D, I, M, a_i \le 255\)

Phân nhóm

• Small dataset (Test set 1): \(1 \le N \le 3\).
• Large dataset (Test set 2): \(1 \le N \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Case #1: 4
Case #2: 17

Nguồn

Google Code Jam 2010, Vòng 1A, bài Make it Smooth.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.