MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

ACM 2014 - Round #3

Ended

A - Pie Problem VI

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Dada una matriz divida en $M \times N$ celdas de lados iguales donde algunos cuadrados son inválidos. ¿Cuál es el cuadrado más grande que se puede obtener sin contener celdas inválidas? Por ejemplo, si en una matriz de $6 \times 9$ hay $3$ celdas inválidas como se muestra en la figura más abajo, entonces la respuesta es $4$ (el cuadrado de $4 \times 4$ dibujado con líneas dobles).

Escriba un algoritmo para resolver este problema.

Input

Línea 1 : Dos enteros $M$ y $N$ $(1 \leq M, N \leq 100)$ separados por espacio, la cantidad de filas y columnas respectivamente. 
Línea 2 : Un solo entero $K$ $(0 \leq K \leq M * N)$, el número de celdas invalidas. 
Línea 3…K+2 : Dos enteros por línea $F_i$ $(1 \leq F_i \leq M)$ y $C_i$  $(1 \leq C_i \leq N)$ separados por espacio, la fila y la columna respectivamente de la $i$-ésima celda invalida. 

Output

Línea 1 : Un solo entero, el lado del mayor cuadrado que no contenga celdas inválidas.

Sample test(s)

Input
6 9 3 2 6 3 2 5 7
Output
4

Hints