Đóng gói tối ưu (Optimal Packing)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ kiện hàng theo thứ tự $1,2,\ldots,N$. Kiện hàng thứ $i$ có khối lượng $A_i\ge 0$. Cần chia toàn bộ dãy kiện hàng thành các nhóm liên tiếp không rỗng. Nếu tổng khối lượng của một nhóm bằng $S$ thì chi phí xử lý nhóm đó là

trong đó $C$ là một hằng số cho trước.

Hãy tìm tổng chi phí nhỏ nhất để chia và xử lý toàn bộ $N$ kiện hàng.

Input

• Dòng đầu chứa hai số nguyên $N,C$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Subtask

• Subtask 1 (40%): $1\le N\le 2000$, $0\le C\le 10^9$, $0\le A_i\le 1000$.
• Subtask 2 (60%): $1\le N\le 2\cdot 10^5$, $0\le C\le 10^9$, $0\le A_i\le 1000$.

Ví dụ

Ví dụ 1

Input

3 10
2 3 4

Output

59

Giải thích

Chia thành ba nhóm riêng lẻ có chi phí $(2^2+10)+(3^2+10)+(4^2+10)=59$, và đây là giá trị nhỏ nhất.

Ví dụ 2

Input

4 100
1 1 1 1

Output

116

Giải thích

Gộp cả bốn kiện thành một nhóm có chi phí $4^2+100=116$, nhỏ hơn mọi cách chia thành nhiều nhóm hơn.