Problem
トム・ソーヤーは友人たちを説得して、ポリーおばさんの家の周りのフェンスにペンキを塗るという難しい仕事に協力してくれるようにした。フェンスは 1 から k までの番号が付けられた k 枚の連続したボードで構成され、k 番目のボードの後に再び最初のボードが来ます。
トムの友達はとても気難しい人で、i 番目の友達は、正確に a 個の連続したボードのセクションをペイントすることが許可されている場合にのみペイントに参加することに同意します。トムはブラシを 1 つしか持っていないので、友達が順番に、割り当てられたセグメント全体を一度にペイントします。トムに残された唯一のことは、友達を招待する順序を選択し、それぞれに必要な連続ボードの数を選択することです。
同時に、トムの友人はそれぞれ、未塗装のフェンス板と、前任者の 1 人がすでに塗装した板の両方をペイントする準備ができています。しかし、友人たちは、塗装されていないボードにペイントすることにより大きな喜びを感じます。トムは数値 x を選択し、各友人が少なくとも x 個の未塗装の板をペイントするように、ペイントするフェンスのセクションを分配したいと考えています。トムは友達をとても愛していて、友達にフェンスのペンキ塗りを最大限に楽しんでもらいたいので、x を最大化しようとします。
トムが友達にどれほどの喜びをもたらすことができるかを理解できるように手伝ってください。
入力データ形式
入力ファイルの最初の行には、2 つの整数 n (1 ≤ n ≤ 10
5 ) と k (1 ≤ k ≤ 10
9 ) が含まれています。次の行には n 個の整数が含まれています。値 a
i (1 ≤ a
i ≤ k)。
出力データ形式
数字を 1 つ出力します。
x の最大値。
<本体>
| 入力 |
出力 |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
説明
最初の例では、友人の 1 人が 5 枚以上のボードをペイントしたくないため、x = 5 になります。彼が最初に来て、自分の 5 枚をペイントし、その後、さらに 10 枚の未塗装のボードがトムの 2 番目の友人に送られます。残りの 85 枚のボードはトム自身がペイントする必要があります。
2 番目の例では、たとえば次のようにして x = 2 に到達できます。まず、3人目の友人がボード4～6（未塗装のボード3枚）を塗ります。次に、4 番目の友人がボード 1 ～ 5 (未塗装のボード 3 枚) をペイントします。次に、2 番目の友人がボード 1 ～ 8 (未塗装のボード 2 枚) をペイントします。最後に、最初の友人はボード 6 ～ 10 と 1 ～ 2 をペイントします (2 つの未塗装のボード。フェンスは循環しており、これらのボードが連続したセグメントを形成していることに注意してください)。