装箱打包

题目背景

工厂的流水线上依次送来 $n$ 件货物，它们必须按原来的先后顺序装箱，不允许打乱次序。每件货物都有固定的重量。厂长给打包机设了一条规则：一只箱子除了装货，还要额外加上 $M$ 千克的固定配重（包装材料与缓冲垫），装箱的代价等于箱内总重量与配重之和的平方。厂长想找到一种装箱方案，让总代价最小。

题目描述

有 $n$ 件货物排成一行，第 $i$ 件货物的重量为 $w_i$（$1 \le w_i \le 1000$）。

你需要把这 $n$ 件货物分成若干段，每一段对应一只箱子，要求每件货物恰好属于一只箱子，并且同一只箱子里的货物在原来的队伍中必须是连续的一段。也就是说，你只需要选择若干个切分点，把整个序列切成若干段，每段首尾相接。

给定常数 $M$（$0 \le M \le 10^4$）。如果一只箱子里货物的总重量为 $S$，那么这只箱子的代价是

请你求出所有装箱方案中，总代价的最小值。

输入格式

从标准输入读入数据。

第一行两个整数 $n, M$。

第二行 $n$ 个整数 $w_1, w_2, \dots, w_n$，依次表示每件货物的重量。

输出格式

输出到标准输出。

一行一个整数，表示最小的总代价。

样例 1 输入

3 2
1 2 3

样例 1 输出

50

样例 1 解释

四种装箱方案的代价分别是：

• 一只箱子装下全部：$(1+2+3+2)^2 = 64$；
• 分成 $[1]$ 与 $[2,3]$：$(1+2)^2 + (5+2)^2 = 9 + 49 = 58$；
• 分成 $[1,2]$ 与 $[3]$：$(3+2)^2 + (3+2)^2 = 25 + 25 = 50$；
• 每件单独一箱：$(1+2)^2 + (2+2)^2 + (3+2)^2 = 9 + 16 + 25 = 50$。

最小总代价是 $50$。

样例 2 输入

4 0
2 2 2 2

样例 2 输出

16

样例 2 解释

$M=0$ 时把四件货物分开装，每只箱子代价 $2^2=4$，总代价 $16$；装在一起是 $8^2=64$，所以分开更优。

数据范围

对全部测试数据，保证 $1 \le n \le 10^5$，$1 \le w_i \le 1000$，$0 \le M \le 10^4$。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。