配点 : $700$ 点

問題文

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

数直線上に $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$ 個のゴミを全てゴミ箱に入れるために必要なエネルギーの最小値を求めてください。

制約

• $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$ のエネルギーを消費して、ゴミを取る
• $36$ のエネルギーを消費して、位置 $1$ に移動する
• $100$ のエネルギーを消費して、ゴミを取る
• $9$ のエネルギーを消費して、位置 $0$ に移動する
• $100$ のエネルギーを消費して、$2$ つのゴミをゴミ箱に入れる

このように行動したとき、消費したエネルギーは $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