配点 : $500$ 点

問題文

長さ $L$ のパンが $1$ つあり、これを $N$ 人の子供たちに切り分けます。 $i$ 番目 $(1\leq i\leq N)$ の子供は長さ $A_i$ のパンを欲しがっています。

そこで、高橋君は次の操作を繰り返して、長さ $A_1,A_2,\ldots,A_N$ のパンを切り出して配ることにしました。

長さ $k$ のパン $1$ つと $1$ 以上 $k-1$ 以下の整数 $x$ を選ぶ。選んだパンを長さ $x$ のパンと 長さ $k-x$ のパンに切り分ける。 このとき、$x$ の値によらずコストが $k$ かかる。

それぞれの子供に配るパンは長さがちょうど $A_i$ のパン $1$ つである必要がありますが、誰にも配られずに余るパンがいくつあっても構いません。

このとき、全ての子供たちにパンを配るために必要な最小のコストを求めてください。

制約

• $2 \leq N \leq 2\times 10^5$
• $1\leq A_i\leq 10^9$
• $A_1+A_2+\cdots+A_N\leq L\leq 10^{15}$
• 入力は全て整数

入力

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

$N$ $L$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

全ての子供たちにパンを配るために必要な最小のコストを出力せよ。

5 7
1 2 1 2 1

16

高橋君は次のようにしてパンを切り分けて配ることができます。

• 長さ $7$ のパンと整数 $x=3$ を選ぶ。パンは長さ $3$ のパンと長さ $4$ のパンに切り分けられる。 (コスト $7$ )
• 長さ $3$ のパンと整数 $x=1$ を選ぶ。パンは長さ $1$ のパンと長さ $2$ のパンに切り分けられる。前者を $1$ 番目の子供に配る。 (コスト $3$ )
• 長さ $2$ のパンと整数 $x=1$ を選ぶ。パンは長さ $1$ のパン $2$ つに切り分けられる。これを $3,5$ 番目の子供に配る。 (コスト $2$ )
• 長さ $4$ のパンと整数 $x=2$ を選ぶ。パンは長さ $2$ のパン $2$ つに切り分けられる。これを $2,4$ 番目の子供に配る。 (コスト $4$ )

このとき、コストは $7+3+2+4=16$ かかり、これが最小です。 また、余るパンはありません。

3 1000000000000000
1000000000 1000000000 1000000000

1000005000000000

それぞれの子供に配るパンの長さはちょうど $A_i$ でなければならない事に注意してください。