Problem
Tom Sawyer convenceu alguns de seus amigos a ajudá-lo na difícil tarefa de pintar a cerca que cercava a casa de tia Polly. A cerca consiste em k pranchas consecutivas, numeradas de 1 a k, e após a k-ésima prancha vem a primeira novamente.
Os amigos de Tom são muito exigentes, o i-ésimo amigo concorda em participar da pintura apenas se tiver permissão para pintar uma seção de exatamente todas as pranchas consecutivas. Tom tem apenas um pincel, então seus amigos pintarão por sua vez e de uma só vez todo o segmento atribuído a eles. A única coisa que resta a Tom é escolher a ordem em que convidará seus amigos, bem como escolher o número desejado de tabuleiros consecutivos para cada um.
Ao mesmo tempo, cada um dos amigos de Tom está pronto para pintar uma cerca sem pintura e uma que já foi pintada por um de seus predecessores. No entanto, os amigos têm mais prazer em pintar uma placa sem pintura. Tom quer escolher um número x e distribuir as seções da cerca a serem pintadas de forma que cada um de seus amigos pinte pelo menos x tábuas sem pintura. Tom ama muito seus amigos e quer que cada um deles tire o máximo proveito da pintura da cerca, então ele tenta maximizar x.
Ajude Tom a entender quanta alegria ele pode trazer para seus amigos.
Formato de dados de entrada
A primeira linha do arquivo de entrada contém dois inteiros n (1 ≤ n ≤ 10
5 ) e k (1 ≤ k ≤ 10
9 ). A próxima linha contém n inteiros — valores a
i (1 ≤ a
i ≤ k).
Formato de dados de saída
Imprima um número — valor máximo possível de
x.
| Entrada |
Saída |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
Explicação
No primeiro exemplo x = 5 porque um dos amigos simplesmente não quer pintar mais do que cinco pranchas. Ele virá primeiro, pintará seus cinco, após o que outras 10 pranchas não pintadas irão para o segundo amigo de Tom. As 85 pranchas restantes terão que ser pintadas pelo próprio Tom.
No segundo exemplo, x = 2 pode ser alcançado, por exemplo, assim. Primeiro, o terceiro amigo pinta as pranchas 4 a 6 (3 pranchas sem pintura). Em seguida, o quarto amigo pinta as pranchas 1 a 5 (3 pranchas sem pintura). Em seguida, o segundo amigo pinta as pranchas 1 a 8 (2 pranchas não pintadas). Por fim, o primeiro amigo pinta as pranchas 6 a 10 e 1 a 2 (2 pranchas não pintadas, observe que a cerca anda em um ciclo e essas pranchas formam um segmento consecutivo).