题目描述

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

在数轴上有 $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

输入

2 100
1 10

输出

355

样例 2

输入

5 1
1 999999997 999999998 999999999 1000000000

输出

19999999983

样例 3

输入

10 8851025
38 87 668 3175 22601 65499 90236 790604 4290609 4894746

输出

150710136

样例 4

输入

16 10
1 7 12 27 52 75 731 13856 395504 534840 1276551 2356789 9384806 19108104 82684732 535447408

输出

3256017715

说明/提示

限制条件

• $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 翻译