Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P131SUMJ - SUM1 J - Đường dây điện thoại

Các con bò của Farmer John đang buồn phiền về dịch vụ điện thoại nghèo nàn của chúng. Chúng muốn FJ thay thế các dây điện thoại cũ bằng cái mới, hiệu quả hơn. Hệ thống dây mới sẽ sử dụng để cài đặt N (2 <= N <= 100 000) cột điện thoại đã có, mỗi cột có chiều cao là h_i (1<= h_i <= 100). Dây mới sẽ kết nối đỉnh của hai cột liền kề nhau và sẽ chịu chi phí là C$ nhân với độ chênh lệch chiều cao của 2 cột (1 <= C <= 100). Tất nhiên những cột điện là cố định vào không thể di chuyển được.

Farmer John hình dung nếu dựng vài cột cao hơn ông ta có thể giảm chi phí. Ông ta có thể thêm một số X (m) cho một cột và mất chi phí là X^2 $.

Giúp Farmer John xác định phương án tối ưu nhất (rẻ tiền nhất) bằng cách tăng chiều cao các cột và kết nối dây cho các con bò có thể nhận được sự cải thiện dịch vụ của mình.

Input

Dòng 1: chứa 2 số nguyên N và C.

Dòng 2 đến N+1: Dòng i+1 là chiều cao của cột điện thứ i, h_i.

Output

In ra số tiền cần phải chi trả cho hệ thống đường dây điện thoại mới.

Example

Input:

5 2
2
3
5
1
4
Output:
15

Giải thích

Input:
Có 5 cột điện thoại, và chi phí là 2$ / 1m. Ban đầu các cột có chiều cao là 2, 3, 5, 1 và 4.

Output:
Cách tốt nhất là cho Farmer John nâng cao cột đầu tiên nên một đơn vị  và cột thứ 4 lên 2 đơn vị để chiều cao là 3, 3, 5, 3, và 4.

Chi phí thêm chiều cao cột là: 2*2 + 1*1 = 5$. Còn hệ thống dây có chi phí là: 2$ * ( 0 + 2 + 2 + 1) = 10$, cho tổng số 15$.

Được gửi lên bởi:Admin
Ngày:2013-07-03
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2013-07-24 01:52:07 Trần Vãn Dương D10CN2
Trau bo cung duoc 4.008 chay qua lau 4.3.2 AC

Last edit: 2013-07-24 01:57:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.