配点: 500点

問題文

長さ NN の配列 AA が与えられます。くしらくんは以下の操作を好きなだけ行い、配列の要素の合計値を SS にしたいです。

  • AiA_i00 より大きい任意のi(1iN)i(1≦i≦N)を選び、コスト AiA_i をかけ、AiA_i11 を加算または減算をする。

目的を達成するために必要なコストの最小値を求めてください。

制約

  • 1N2×1051≦N≦2×10^5
  • 1S10101≦S≦10^{10}
  • 1Ai1051≦A_i≦10^5
  • 入力はすべて整数である

入力

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

N S
A_1 A_2 ... A_N

出力

答えを出力してください。


入出力例1

・入力

3 5
2 1 4

・出力

3

以下の操作をすることで目標を達成できます。

  • i=1i=1 を選び、11 を減算する。コストは2かかる。
  • i=2i=2 を選び、11 を減算する。コストは1かかる。 コストの総和を 33 より小さくできないので3を出力します。

入出力例2

・入力

4 15
1 3 4 1

・出力

12

入出力例3

・入力

5 22
1 3 3 4 7

・出力

9

入出力例4

・入力

4 4
1 1 1 1

・出力

0

操作をしないでも目標は達成されています。

Submit


Go (1.21)