Descripción

El doctor OCI-Cub está preocupado por la salud de sus pacientes después de un brote de la altamente contagiosa enfermedad humana COVID-19.

Para limitar la transmisión de la enfermedad, los ~N~ pacientes del doctor OCI-Cub han decidido practicar "distanciamiento social" y distribuirse por toda la provincia.

La provincia tiene forma de recta numérica unidimensional, con ~M~ intervalos disjuntos en los que hay césped para ellos.

Los pacientes quieren posicionarse en distintos puntos enteros, todos con césped, tal que se maximice el valor de ~D~, donde ~D~ representa la distancia entre el par más cercano de pacientes.

Tarea

Determina el máximo valor posible de ~D~.

Entrada

La primera línea de contiene ~N~ y ~M~.

Cada una de las siguientes ~M~ líneas contienen dos enteros ~a_i~ y ~b_i~, el inicio y fin de cada intervalo, ningún par de intervalos se cruza ni se toca en los extremos, un paciente parado en alguno de los extremos se considera que está dentro del césped.

Salida

Imprime el máximo valor de ~D~ tal que todos los pares de pacientes estén a distancia al menos ~D~, se garantiza que una solución con ~D > 0~ existe.

Restricciones

~1 \leq N \leq 10^5~

~1 \leq M \leq 10^5~

~0 \leq a \leq b \leq 10^{18}~

Subtareas

Casos 2-3: ~0 \leq a \leq b \leq 10^5~

Casos 4-10: Sin restricciones adicionales

Entrada ejemplo

5 3
0 2
4 7
9 9

Salida ejemplo

2

Una forma de obtener ~D = 2~ es poner a las pacientes en las posiciones 0, 2, 4, 6 y 9.