Đèn lồng

Trên trục đường phố chính của thành phố Thái Nguyên có $n$ tòa nhà, được đánh số theo thứ tự từ $1$ đến $n$, tòa nhà thứ $i$ có chiều cao là một số nguyên dương $h_i$.

Để chuẩn bị cho Mùa du lịch Thái Nguyên năm nay, thành phố lập kế hoạch treo đèn lồng trang trí cho các tòa nhà. Hai tòa nhà liền kề $i$ và $i+1$ mất chi phí $c·|h_i-h_{i+1}|$ ($c$ là hằng số). Chi phí của trục đường là tổng chi phí của các tòa nhà kề nhau, tức là $S=c·{\sum }_{i=1}^{n-1}|h_i-h_{i+1}|$. Thành phố đẹp nhất khi các con đường đều đẹp nhất. Tuy nhiên, do nguồn kinh phí có hạn, lãnh đạo thành phố quyết định chọn giải pháp tu sửa nâng chiều cao một số ngôi nhà để tiết kiệm chi phí, cụ thể nếu tòa nhà $i$ nâng chiều cao thêm $x$ (đơn vị, $x>0$) thì thành phố phải mất một khoản chi phí là $x^2$.

Chiều cao chỉ được nâng lên (không được hạ xuống), mỗi tòa nhà được nâng thêm một số nguyên đơn vị (có thể không nâng). Chi phí thành phố phải trả là tổng chi phí treo đèn lồng $S$ tính theo chiều cao mới cộng với tổng chi phí nâng các tòa nhà.

Yêu cầu: Cho biết $n$, $c$ và các chiều cao $h_i$ ($i=1,\dots ,n$), bạn hãy giúp thành phố tính chi phí thấp nhất khi thực hiện theo kế hoạch.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n,c$ ($1\le n\le {10}^4$, $1\le c\le {10}^6$).
• Mỗi dòng trong $n$ dòng sau chứa một số nguyên $h_i$ ($1\le h_i\le 1000$).

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

Một số nguyên là chi phí thấp nhất mà thành phố phải trả.

Ràng buộc

• $1\le n\le {10}^4$.
• $1\le c\le {10}^6$.
• $1\le h_i\le 1000$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n\le 10$; $h_i\le 3$.
• Subtask 2 ($40\%$ số điểm): $n\le 1000$; $h_i\le 100$.
• Subtask 3 ($30\%$ số điểm): $n\le 10000$; $h_i\le 1000$.

Ví dụ