Problem
Tom Sawyer a persuadé n de ses amis de l'aider dans la tâche difficile de peindre la clôture entourant la maison de tante Polly. La clôture se compose de k planches consécutives, numérotées de 1 à k, et après la k-ième planche vient à nouveau la première.
Les amis de Tom sont très pointilleux, le i-ème ami n'accepte de participer à la peinture que s'il est autorisé à peindre une section d'exactement ai des planches consécutives. Tom n'a qu'un seul pinceau, alors ses amis vont peindre à tour de rôle et d'un coup tout le segment qui leur est attribué. Il ne reste plus à Tom qu'à choisir l'ordre dans lequel inviter ses amis, ainsi qu'à choisir le nombre de planches consécutives souhaitées pour chacun.
Dans le même temps, chacun des amis de Tom est prêt à peindre à la fois une planche de clôture non peinte et une planche déjà peinte par l'un de ses prédécesseurs. Cependant, les amis ont plus de plaisir à peindre une planche non peinte. Tom veut choisir un nombre x et répartir les sections de clôture à peindre de manière à ce que chacun de ses amis peigne au moins x planches non peintes. Tom aime beaucoup ses amis et veut que chacun d'eux tire le meilleur parti de la peinture de la clôture, alors il essaie de maximiser x.
Aidez Tom à comprendre la joie qu'il peut apporter à ses amis.
Format des données d'entrée
La première ligne du fichier d'entrée contient deux entiers n (1 ≤ n ≤ 10
5 ) et k (1 ≤ k ≤ 10
9 ). La ligne suivante contient n entiers — valeurs a
i (1 ≤ a
i ≤ k).
Format des données de sortie
Imprimer un numéro — valeur maximale possible de
x.
| Entrée |
Sortie |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
Explication
Dans le premier exemple x = 5 car l'un des amis ne veut tout simplement pas peindre plus de cinq planches. Il viendra en premier, peindra ses cinq, après quoi 10 autres planches non peintes iront au deuxième ami de Tom. Les 85 planches restantes devront être peintes par Tom lui-même.
Dans le deuxième exemple, x = 2 peut être atteint, par exemple, comme ceci. Dans un premier temps, le troisième ami peint les planches 4 à 6 (3 planches non peintes). Puis le quatrième ami peint les planches 1 à 5 (3 planches non peintes). Puis le deuxième ami peint les planches 1 à 8 (2 planches non peintes). Enfin, le premier ami peint les planches 6 à 10 et 1 à 2 (2 planches non peintes, notez que la clôture va dans un cycle et ces planches forment un segment consécutif).