AT_agc027_b.[AGC027B] Garbage Collector

すぬけ君决定用扫地机器人来打扫房间。

在数轴上有 $N$ 个垃圾。第 $i$ 个垃圾位于位置 $x_i$。他想把这些垃圾都放进位于位置 $0$ 的垃圾箱里。

关于垃圾的位置，满足 $0 < x_1 < x_2 < ... < x_N \leq 10^{9}$。

扫地机器人一开始在位置 $0$。机器人可以在数轴上自由移动，移动到有垃圾的位置时可以捡起垃圾。机器人可以同时携带任意数量的垃圾，移动到垃圾箱的位置时可以将携带的垃圾全部放入垃圾箱。除了垃圾箱以外，不能在其他地方放下垃圾。

每当机器人捡起垃圾，或者将（一个或多个）垃圾放入垃圾箱时，会消耗 $X$ 的能量。无论一次放入多少个垃圾，消耗的能量都是 $X$。另外，当机器人携带 $k$ 个垃圾时，每移动 $1$ 的距离会消耗 $(k+1)^2$ 的能量。

请你求出将所有 $N$ 个垃圾都放入垃圾箱所需的最小能量。

输入通过标准输入给出，格式如下：

$N$ $X$ $x_1$ $x_2$ $...$ $x_N$

请输出答案。

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $0 < x_1 < x_2 < ... < x_N \leq 10^9$
• $1 \leq X \leq 10^9$
• 所有输入均为整数

部分得分

• 对于 $N \leq 2000$ 的数据集，满分为 $400$ 分。

样例说明 1

• 消耗 $10$ 的能量移动到位置 $10$
• 消耗 $100$ 的能量捡起垃圾
• 消耗 $36$ 的能量移动到位置 $1$
• 消耗 $100$ 的能量捡起垃圾
• 消耗 $9$ 的能量移动到位置 $0$
• 消耗 $100$ 的能量将 $2$ 个垃圾放入垃圾箱

如此行动时，总共消耗的能量为 $10+100+36+100+9+100=355$。

由 ChatGPT 4.1 翻译