好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：HDU 3507

给出 $N$ 个单词，每个单词有个非负权值 $C_i$，现要将它们分成连续的若干段，每段的代价为此段单词的权值和的平方，还要加一个常数 $M$，即 $(\sum C_i)^2 + M$。现在想求出一种最优方案，使得总费用之和最小。

---

输入格式

包含多组测试数据，对于每组测试数据：

第一行包含两个整数 $N$ 和 $M$。

第二行为 $N$ 个整数 $C_1, C_2, \dots, C_N$。

输入以 EOF（文件结束）终止。

---

输出格式

对于每组数据，输出一行一个整数，表示最小的总费用。

---

样例

样例输入

5 5
5 9 5 7 5

样例输出

230

样例说明

$N=5, M=5$，单词权值 $[5,9,5,7,5]$。

设前缀和 $S_i = \sum_{k=1}^i C_k$，则分段 $[j+1, i]$ 的代价为 $(S_i - S_j)^2 + M$。

我们需要将序列分成若干段，使总代价最小。

一种最优分段：

• 第一段：[5,9,5] 和 $=19$，代价 $19^2+5=361+5=366$
• 第二段：[7,5] 和 $=12$，代价 $144+5=149$
  总代价 $366+149=515$，不是 230。

显然 230 更小，说明分段更细。
尝试全部分开：
(5) 25+5=30
(9) 81+5=86
(5) 25+5=30
(7) 49+5=54
(5) 25+5=30
总和 230。

因此样例最优方案是每个单词单独成一段。

---

数据范围

对于全部数据：

• $0 \le N \le 5\times 10^5$
• $0 \le M \le 1000$
• $C_i \ge 0$（非负）

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 斜率优化 DP 经典题。

状态设计：
设 $dp[i]$ 表示前 $i$ 个单词分成若干段的最小总费用。

转移方程：
考虑最后一段为 $(j+1, j+2, \dots, i)$，则：

$$dp[i] = \min_{0 \le j < i} \left\{ dp[j] + (S_i - S_j)^2 + M \right\}$$

其中 $S_i$ 是 $C_i$ 的前缀和。

展开：

$$dp[i] = \min_{0 \le j < i} \left\{ dp[j] + S_i^2 - 2S_i S_j + S_j^2 + M \right\}$$

合并与 $j$ 无关的项：

$$dp[i] = S_i^2 + M + \min_{0 \le j < i} \left\{ dp[j] - 2S_i S_j + S_j^2 \right\}$$

令 $A_j = S_j$, $B_j = dp[j] + S_j^2$，则：

$$dp[i] = S_i^2 + M + \min_{0 \le j < i} \left\{ B_j - 2S_i A_j \right\}$$

斜率优化：
对于 $j_1 < j_2$，决策 $j_2$ 优于 $j_1$ 的条件为：

$$\frac{B_{j_2} - B_{j_1}}{A_{j_2} - A_{j_1}} \le 2S_i$$

由于 $S_i$ 单调非降（$C_i \ge 0$），$A_j$ 单调递增，因此可以用单调队列维护下凸包，队首为最优决策。

步骤：

1. 计算前缀和 $S_i$；
2. 初始化队列，将 $j=0$ 入队（$A_0=0, B_0=0$）；
3. 遍历 $i$ 从 $1$ 到 $N$：
   • 若队首两点斜率 $\le 2S_i$，则弹出队首；
   • 取队首 $j$ 计算 $dp[i]$；
   • 将 $(A_i, B_i)$ 加入队尾，维护凸包（弹出队尾上凸点）；
4. 输出 $dp[N]$。

复杂度 $O(N)$，可以处理 $N$ 高达 $5\times 10^5$ 的数据。

注意：

• 有多组测试数据，需要清空队列等；
• 当 $N=0$ 时，总费用为 $0$；
• 使用 long long 存储中间结果，避免溢出。