Chia Bản Thảo · canuc80k4207

Cho một dãy số không âm và hằng số $m$ . Bạn phải chia dãy thành các đoạn liên tiếp không rỗng.

Nếu tổng phần tử của một đoạn là $s$ , chi phí của đoạn bằng $s^{2} + m$ . Hãy tìm tổng chi phí nhỏ nhất. Input có thể chứa nhiều bộ dữ liệu liên tiếp cho đến hết tệp.

Input

Mỗi bộ dữ liệu bắt đầu bằng $n$ $m$ .
Dòng tiếp theo chứa $n$ phần tử của dãy.
Các bộ dữ liệu xuất hiện liên tiếp cho đến EOF.

Output

Với mỗi bộ dữ liệu, in đáp án trên một dòng.

Constraints

$1 \leq n \leq 5 \cdot 1 0^{5}$ cho mỗi bộ.
$0 \leq m \leq 1 0^{9}$ .
$0 \leq a_{i} \leq 100$ .
Mọi đáp án nằm trong miền số nguyên có dấu $64$ -bit.

Scoring

Subtask $1$ ( $50%$ số điểm): kích thước chính không vượt quá $60$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

4 2
1 2 1 3

Output

Giải thích: Chia thành bốn đoạn đơn [1], [2], [1], [3] cho chi phí $1^{2} + 2 + 2^{2} + 2 + 1^{2} + 2 + 3^{2} + 2 = 23$ . Mọi cách ghép hai hay nhiều phần tử trong ví dụ đều cho tổng lớn hơn.