JOI-kun y sus amigos jugarán con bengalas. En total, hay ~N~ personas, incluyendo a JOI-kun y sus amigos. Si alguien enciende una bengala, esta se mantiene encendida durante exactamente ~T~ segundos.

Al principio, JOI-kun y sus amigos están de pie por separado a lo largo de una calle recta que va de este oeste. JOI-kun y sus amigos están numerados del ~1~ al ~N~. Para cada ~i~, ~j~ con ~i < j~, la persona ~i~ está de pie al oeste de la persona ~j~, o bien la persona ~i~ y la persona ~j~ están en el mismo lugar. La distancia desde la persona ~i~ hasta la persona más al oeste (es decir, la primera persona) es de ~X_i~ metros. JOI-kun es la ~K-~ésima persona.

Cuando empiezan a jugar con las bengalas, se dan cuenta de que el encendedor no tiene suficiente combustible. Solo pueden encender una bengala.

Así que deciden prenderle fuego primero a la bengala de JOI-kun. Luego, encenderán otras bengalas tocándolas con bengalas encendidas.

Como una bengala solo mantiene el fuego durante ~T~ segundos, JOI-kun y sus amigos deben cooperar para propagar el fuego a las bengalas. Al encender una bengala tocándola con una encendida, deben cumplirse las siguientes condiciones:

• Deben tocar una bengala con una encendida dentro de los ~T~ segundos posteriores a encenderla. Pueden hacerlo después de que han transcurrido exactamente ~T~ segundos.
• La bengala que planean encender no debe estar encendida previamente.
• La persona que tiene una bengala encendida y la persona que tiene una bengala apagada deben estar en el mismo lugar.

Ignoramos el tiempo de espera para encender una bengala tras otra.

Como JOI-kun y sus amigos están separados al principio, deben moverse adecuadamente para propagar el fuego. Pueden correr a cualquier velocidad hacia el oeste o el este. Sin embargo, es peligroso correr demasiado rápido cuando juegan. Por lo tanto, establecerán una regla: su velocidad no debe exceder ~s~ metros por segundo. Aquí, ~s~ es un número entero no negativo. ¿Cómo deben establecer el límite de velocidad para que el fuego se propague a todas las bengalas?

Escribe un programa que calcule el número entero mínimo ~s~ para que puedan propagar el fuego a todas las bengalas si el límite de velocidad es de ~s~ metros por segundo.

Entrada

La primera línea de entrada contiene tres enteros separados por espacios: ~N~, ~K~, ~T~ (~1 \leq K \leq N \leq 10^5~, ~1 \leq T \leq 10^9~)~-~ hay ~N~ personas, JOI-kun es la ~K-~ésima persona, y una bengala mantiene el fuego durante ~T~ segundos.

La ~i-~ésima línea (~1 \leq i \leq N~) de las siguientes ~N~ líneas contiene un entero ~X_i~ (~0 \leq X_i \leq 10^9~) ~-~ al inicio, la distancia desde la persona ~i~ hasta la persona más al oeste es de ~X_i~ metros. Se asegura que ~X_1 = 0~ y que ~X_i \leq X_j~ para ~1 \leq i \leq j \leq N~.

Salida

La salida contiene el mínimo entero ~s~ necesario para que puedan propagar el fuego a todas las bengalas si el límite de velocidad es de ~s~ metros por segundo.

Subtareas

Subtarea	Puntos	Restricciones adicionales
~1~	~30~	~N \leq 20~
~2~	~20~	~N \leq 1 000~
~3~	~50~	Sin restricciones adicionales

Ejemplos

Entrada 1

3 2 50
0
200
300

Salida 1

2

En este ejemplo, el límite de velocidad es de ~2~ metros por segundo.

La primera persona se mueve hacia el este, la segunda hacia el oeste y la tercera hacia el oeste; su velocidad es de ~2~ metros por segundo. Después de ~50~ segundos, la segunda persona le da fuego a la primera.

Luego, la primera persona se mueve hacia el este y la tercera hacia el oeste; su velocidad es de ~2~ metros por segundo. Después de ~25~ segundos, la primera persona le da fuego a la tercera.

Si el límite de velocidad es de ~1~ metro por segundo, no pueden propagar el fuego a todas las bengalas.

Entrada 2

3 2 10
0
200
300

Salida 2

8

En este ejemplo, el límite de velocidad puede ser de ~8~ metros por segundo.

La primera persona se mueve hacia el este, la segunda persona se mueve hacia el este y la tercera persona se mueve hacia el oeste; su velocidad es de ~8~ metros por segundo.

Después de ~3~ segundos, la segunda persona se detiene. La primera y la tercera persona continúan moviéndose.

Después de ~6.5~ segundos más, la segunda y la tercera persona llegan al mismo lugar. Pero no propagan el fuego. La segunda y la tercera persona se detienen. La primera persona continúa moviéndose.

Después de ~0.5~ segundos más, la segunda persona le da fuego a la tercera persona. La primera persona continúa moviéndose. La tercera persona se mueve hacia el oeste; su velocidad es de ~8~ metros por segundo.

Después de ~9~ segundos más, la primera y la tercera persona llegan al mismo lugar. La tercera persona le da fuego a la primera persona.

Si el límite de velocidad es de ~7~ metro por segundo, no pueden propagar el fuego a todas las bengalas.