밭 구역 나누기

문제

한 줄로 늘어선 N개의 밭이 있다. i번째 밭에는 토양 수분 편차 지수 a_i 가 측정되어 있으며, 기준보다 건조하면 양수, 습하면 음수인 정수이다.\n\n농부는 밭을 앞에서부터 차례로 끊어 연속한 구역 여러 개로 나누어 관리하려 한다. 모든 밭은 정확히 하나의 구역에 속해야 하고, 구역은 적어도 밭 하나를 포함한다. 한 구역을 관리하는 비용은 C와, 그 구역에 속한 밭들의 a 값을 모두 더한 합의 제곱을 더한 값이다. 즉 구역이 l번부터 r번 밭까지라면 비용은 C + (a_l + a_{l+1} + ... + a_r)^2 이다.\n\n밭을 구역으로 나누는 방법은 자유롭다. 모든 구역의 관리 비용을 합한 값이 최소가 되도록 나눌 때, 그 최솟값을 구하여라.

입력

첫째 줄에 N과 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ C ≤ 10^9)\n둘째 줄에 a_1, a_2, ..., a_N 이 공백으로 구분되어 주어진다. (-1000 ≤ a_i ≤ 1000, 정수)

출력

비용 합의 최솟값을 한 줄에 출력한다.

3 1
1 -1 1

2

3 3
2 2 2

21

4 1
3 -1 -1 3

10

출처: Devin.KR 자체 제작