题目描述

すぬけ君は掃除ロボットを使って部屋を掃除することにしました。

数直線上に $N$ 個のゴミが落ちています。 左から $i$ 番目のゴミは位置 $x_i$ にあります。 これらのゴミを位置 $0$ にあるゴミ箱に入れたいです。

ゴミの位置に関して、$ 0\ <\ x_1\ <\ x_2\ <\ ...\ <\ x_{N}\ \leq\ 10^{9} $ が成立します。

掃除ロボットははじめ位置 $0$ にいます。ロボットは数直線上を自由に動くことができ、ゴミのある位置にいくとゴミを拾うことができます。 ゴミは同時に何個でも運ぶことでき、ゴミ箱の位置に行くとゴミをゴミ箱に入れることができます。ゴミをゴミ箱以外の場所に置くことは許されません。

ロボットがゴミを拾う、あるいは($1$ 個以上の)ゴミをゴミ箱に入れるとき $X$ だけエネルギーを消費します。ゴミをゴミ箱に入れるときに消費するエネルギーはゴミの個数にかかわらず $X$ です。 また、ロボットが $k$ 個のゴミを運んでいるとき、距離 $1$ だけ移動するのに $(k+1)^{2}$ だけエネルギーを消費します。

$N$ 個のゴミを全てゴミ箱に入れるために必要なエネルギーの最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

一个数轴上有 $n$ 个垃圾，它们的位置分别为 $x_1,x_2,…,x_n(0<x_1<x_2<…<x_n \le 10^9)$，有一个机器人开始时在位置 $0$ 上，它每个时刻可以选择左右移动或者捡起一个垃圾，当它回到位置 $0$ 时可以把手上的垃圾都扔掉。注意，不能将垃圾扔在除位置 $0$ 以外的位置。

当机器人手上有 $k$ 个垃圾时，走 $1$ 的距离需要消耗 $(k+1)^2$ 的能量，机器人单次捡垃圾或者丢垃圾都需要 $X$ 的能量。如果一次性丢多个垃圾，也只需要 $X$ 的能量。

求机器人把所有垃圾都扔到垃圾桶里最少需要多少能量。

$n\le2\times 10^5$。

2 100
1 10

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

提示

制約

• $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$ 点が与えられる。

Sample Explanation 1

- $10$ のエネルギーを消費して、位置 $10$ に移動する - $100$ のエネルギーを消費して、ゴミを取る - $36$ のエネルギーを消費して、位置 $1$ に移動する - $100$ のエネルギーを消費して、ゴミを取る - $9$ のエネルギーを消費して、位置 $0$ に移動する - $100$ のエネルギーを消費して、$2$ つのゴミをゴミ箱に入れる このように行動したとき、消費したエネルギーは $10+100+36+100+9+100=355$ となります。