Story

🚪

Xmasrate君は無事、まるで巡回セールスマン問題の最適解を辿るかのように各家を周りながら、プレゼントを全て渡すことができました。子どもたちもすごく嬉しそうな顔をしていたので、ほっこりです。

一方ラ亭では、

「失礼します。こちらのお皿をお下げしてもよろしいでしょうか？ありがとうございます！」

greenrate君はかなり忙しそうです。というのもラ亭はUnionFind町の中で人気のお店なので、逆に嬉しいまでありました。

そんな中、matcharate君とwhiteさんが雪まみれになりながら帰ってきました。

greenrate君は、やっと帰ってきたという顔をしています。

「遅いよー！めっちゃ大変なんだからこっちもーもっと早く帰ってきてー！！」

matcharate君は、はーいと返事をしました。greenrate君はやれやれ、という顔をしていました。

:

え、前置きが長い？確かに。では本題に入りましょう。

ラ亭には、クリスマスの雰囲気がありません。そこでgreenrate君は、matcharate君たちにこう言いました。

「机にあるクルミを鈴の中に入れて、その鈴をそこにあるクリスマスリースに付けて、それ入口前に飾っておいて！」

matcharate君は納得しました。せっかくなので、均等に分けながら入れ、量を均等にしようと思いました。

問題

$N$ 個の鈴があります。それぞれ鈴には $1,2,\dots ,N$ と番号づけられており、最初鈴 $i$ には $A_i$ 個のクルミの実が入っています。
また机の上に $W$ 個のクルミの実が置かれています。

今からrate君は次の操作を、机の上にあるクルミの実が無くなるまで好きなだけ行うことができます。

• 現時点で机にあるクルミの実の個数を $w$ とする。$1$ 以上 $N$ 以下の整数 $i$ と、$0$ 以上 $w$ 以下の整数 $v$ を選び、鈴 $i$ に $v$ 個のクルミの実を入れる。 このとき入れた鈴に入れたクルミの実を机の上に戻してはいけない。

なおこの操作の後、机にあるクルミの実をすべて使い切らなくても構いません。

操作後、鈴に入っているクルミの実の個数の最大値、最小値をそれぞれ $M,m$ とします。
適切に操作をした後、$M-m$ の最小値としてありえる値はいくつですか？

入力

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

制約

• $2\le N\le 10^5$
• $1\le W\le 10^9$
• $0\le A_i\le 10^5$
• 入力はすべて整数

出力

答えを出力せよ。

入出力例

5 3
4 2 6 1 7

4

例えば鈴 $2$ に $1$ つ、鈴 $4$ に $2$ つ入れることで $M-m=7-3=4$ にすることができ、これが最小です。

4 4000
1 2 2 5

0

鈴に入っているクルミの実の個数をすべて $5$ に揃えることで達成できます。クルミの実が $3990$ 個だけ余りますが、問題ありません。

5 1
10 10 9 0 1

9