Copiado al portapapeles
Descripción
Lucho es un programador principiante, la informática es su materia favorita. Pronto su maestro de informática va a celebrar un cumpleaños y Lucho ha decidido prepararle un regalo. El plantó n flores en una fila en el alféizar de su ventana y comenzó a esperar a que crecieran.
Sin embargo, después de un tiempo, Lucho notó que las flores dejaron de crecer. Lucho piensa que es de mala educación presentar pequeñas flores. Así que decidió proponer algunas soluciones.
Quedan m días para el cumpleaños. La altura de la i-ésima flor (suponga que las flores en la fila están numeradas del 1 al n de izquierda a derecha) es igual a Ai en este momento. En cada uno de los m días restantes, Lucho puede tomar un riego especial y regar w flores contiguas (puede hacerlo solo una vez al día).
En ese momento, cada flor regada crece una unidad de altura en ese día. Lucho quiere que la altura de la flor más pequeña sea lo más grande posible al final. ¿Qué altura máxima de la flor más pequeña puede obtener?
Entrada
La primera línea contiene tres números enteros separados por un espacio n , m y w (1 ≤ w ≤ n ≤ 10 5 ; 1 ≤ m ≤ 10 5 ) . La segunda línea contiene enteros separados por espacios a1, a2, ..., an (1 ≤ ai ≤ 10 9 )
Salida
Imprima un solo entero: la altura final máxima de la flor más pequeña.
Ejemplo Entrada
6 2 3 2 2 2 2 1 1
Ejemplo Salida
2