Problem
Tom Sawyer überredete n seine Freunde, ihm bei der schwierigen Aufgabe zu helfen, den Zaun rund um das Haus von Tante Polly zu bemalen. Der Zaun ist ein k von aufeinanderfolgenden Brettern, die von 1 bis k nummeriert sind, wobei nach dem k-te Brett wieder das erste kommt.
Toms Freunde sind sehr wählerisch, mein Freund stimmt zu, nur am Malen teilzunehmen, wenn er einen Bereich aus genau aufeinanderfolgenden Brettern bemalen darf. Tom hat nur einen Pinsel, also werden Freunde abwechselnd malen und sofort das gesamte von ihm zugeteilte Segment malen. Es bleibt nur übrig, die Reihenfolge zu wählen, in der Freunde eingeladen werden sollen, und die gewünschte Anzahl aufeinanderfolgender Boards für jeden auszuwählen.
Dabei ist jeder von Toms Freunden bereit, sowohl das noch unlackierte Zaunbrett als auch das bereits von einem seiner Vorgänger bemalte Brett zu malen. Freunde haben jedoch mehr Freude daran, ein unlackiertes Brett zu bemalen. Tom möchte die Anzahl x auswählen und die Zaunabschnitte so verteilen, dass jeder seiner Freunde mindestens x der unlackierten Bretter bemalt. Tom liebt seine Freunde sehr und möchte, dass jeder von ihnen den maximalen Spaß am Lackieren des Zauns erhält, also versucht er, das x zu maximieren.
Helfen Sie Tom zu verstehen, wie viel Freude er seinen Freunden bringen kann.
Eingabeformat
Die erste Zeile der Eingabedatei enthält zwei ganze Zahlen n (1 ≤ n ≤ 10
5 ) und k (1 ≤ k ≤ 10
9 ). Die nächste Zeile enthält n ganze Zahlen — Werte von a
i (1≤ a
i ≤ k).
Ausgabeformat
Geben Sie eine Zahl aus. der maximal mögliche Wert ist
x.
| Eingabe |
Ausgabe |
2 100
5 10 |
5 |
4 10
7 8 3 5 |
2 |
Erklärung
Im ersten Beispiel ist x = 5, da einer der Freunde einfach nicht mehr als fünf Bretter malen möchte. Er wird zuerst kommen, seine fünf malen und dann wird Toms zweiter Freund 10 weitere unlackierte Bretter bekommen. Die restlichen 85 Bretter muss er selbst anmalen.
Im zweiten Beispiel kann man zum Beispiel so x = 2 erreichen. Zuerst malt ein dritter Freund die Bretter 4 bis 6 (3 unlackierte Bretter). Dann färbt der vierte Freund die Bretter 1 bis 5 (3 unlackierte Bretter). Dann färbt ein zweiter Freund die Bretter 1 bis 8 (2 unlackierte Bretter). Schließlich färbt der erste Freund die Bretter 6 bis 10 und 1 bis 2 (2 unlackierte Bretter, beachten Sie, dass der Zaun einen Zyklus durchläuft und diese Bretter einen aufeinanderfolgenden Abschnitt bilden).