分数 : $700$ 分

问题陈述

Snuke 决定使用一个机器人来清理他的房间。

在数轴上有 $N$ 块垃圾。
第 $i$ 块垃圾从左边数起位于位置 $x_i$。
我们希望将它们全部放入位置 $0$ 的垃圾桶中。

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

机器人最初位于位置 $0$。
它可以在数轴上自由移动，来到某个垃圾的位置时捡起那块垃圾，可以携带任意数量的垃圾，并在到达位置 $0$ 时将它们放入垃圾桶。
不允许将垃圾放在垃圾桶以外的地方。

机器人在捡起一块垃圾或将垃圾放入垃圾桶时消耗 $X$ 点能量。
（放入任意数量的垃圾到垃圾桶消耗 $X$ 点能量。）
此外，机器人在携带 $k$ 块垃圾时，移动 $1$ 的距离消耗 $(k+1)^{2}$ 点能量。

找出将所有 $N$ 块垃圾放入垃圾桶所需的最小能量。

约束条件

• $1 \leq N \leq 2 \times 10^{5}$
• $0 < x_1 < ... < x_N \leq 10^9$
• $1 \leq X \leq 10^9$
• 输入中的所有值都是整数。

部分分数

• 对于满足 $N \leq 2000$ 的测试集，将奖励 $400$ 分。

输入

输入格式如下所示，从标准输入中给出：

$N$ $X$

$x_1$ $x_2$ $...$ $x_{N}$

输出

打印答案。

2 100
1 10

355

• 移动到位置 $10$ 消耗 $10$ 点能量。
• 捡起那块垃圾消耗 $100$ 点能量。
• 移动到位置 $1$ 消耗 $36$ 点能量。
• 捡起那块垃圾消耗 $100$ 点能量。
• 移动到位置 $0$ 消耗 $9$ 点能量。
• 将两块垃圾放入垃圾桶消耗 $100$ 点能量。

这个策略总共消耗了 $10 + 100 + 36 + 100 + 9 + 100 = 355$ 点能量。

5 1
1 999999997 999999998 999999999 1000000000

19999999983

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

150710136

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

3256017715