#814. POLE2 - Cột điện 2

Công ty điện lực XYZ có nhiệm vụ cung cấp điện cho thành phố VT. Để cung cấp điện cho thành phố công ty đã cho lắp đặt một hệ thống gồm cột điện được đánh số theo thứ tự từ đến , cột điện thứ có chiều cao là một số nguyên dương , các dây điện được nối giữa các cột liền kề, tức là nối từ cột đến cột , từ cột đến cột ,…., từ cột đến cột . Vì mỹ quan đô thị, thành phố VT đã đưa ra quy định sẽ thu của công ty XYZ một khoản chi phí cho hai cột điện liền kề và là ( là giá chi phí cho mỗi đơn vị chênh lệch chiều cao giữa cột điện liền kề), tổng chi phí là

Đồng thời, thành phố cũng yêu cầu cột điện cạnh nhau có chênh lệch không được phép vượt quá .

Để giảm thiểu chi phí, lãnh đạo công ty đã quyết định chọn giải pháp cho lắp đặt nâng chiều cao một số cột điện. Tuy nhiên, nếu cột điện nâng chiều cao thêm (đơn vị) thì công ty phải mất một khoản chi phí là .

Yêu cầu: Cho biết , các hệ số và các chiều cao , bạn hãy giúp công ty XYZ tính chi phí thấp nhất khi công ty thực hiện theo giải pháp của lãnh đạo công ty.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ;
• Dòng thứ hai chứa số nguyên dương ;
• Dòng thứ ba chứa số nguyên dương .

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

• Ghi ra một số nguyên là chi phí thấp nhất mà công ty XYZ phải trả.

Ví dụ:

Dữ liệu vào:

5 4
2 2 2 2
2 3 5 1 4

Dữ liệu ra:

15

Giải thích:

• Nâng cột thêm , nâng cột thêm . Khi đó chiều cao các cột lần lượt là: . Tổng chi phí là: .

Giới hạn:

• Có số test ứng với số điểm có ;
• Có số test khác ứng với số điểm có ;
• Có số test khác ứng với số điểm có ;
• Có số test còn lại ứng với số điểm có .