Una empresa desea comprar un robot de limpieza de forma cuadrada para limpiar una habitación de forma rectangular. Algunas partes de la habitación están obstruidas.

Existen diferentes robots de distintos tamaños. Cada robot puede moverse horizontal y verticalmente en la habitación si ninguna parte del robot intersecta una obstrucción. Son incapaces de cambiar de orientación, por lo que los movimientos siempre están alineados con los ejes. Los robots más grandes terminarán el trabajo más rápido, pero es más probable que se vean obstaculizados por las obstrucciones. El robot debe permanecer siempre completamente dentro de la habitación, sin que ninguna parte sobresalga de los bordes del rectángulo.

¿Cuál es el robot más grande que la empresa puede comprar que sea capaz de limpiar todos los cuadrados de la habitación no ocupados por obstrucciones?

Entrada

La primera línea de la entrada contiene tres enteros $n$, $m$ ($3 \le n, m$ y $n \cdot m \le 5 \cdot 10^6$) y $k$ ($0 \le k < n \cdot m$, $k < 10^6$), donde $n$ y $m$ son las dimensiones de la habitación en pulgadas, y $k$ es el número de obstrucciones.

Cada una de las siguientes $k$ líneas contiene dos enteros $i$ y $j$ ($1 \le i \le n$, $1 \le j \le m$). Esto especifica que el cuadrado de una pulgada en $(i, j)$ está obstruido. Todos los cuadrados obstruidos son distintos.

Salida

Imprima un solo entero, que es la longitud máxima de un lado del robot cuadrado más grande que podría limpiar toda la habitación, o $-1$ si ningún robot de este tipo pudiera limpiar toda la habitación.

Ejemplos

Entrada 1

10 7 1
8 3

Salida 1

2