El Granjero Juan tiene ~N~ vacas con manchas y ~N~ vacas sin manchas. Acabando de completar un curso en genética bovina, él está convencido que las manchas en sus vacas están causadas por mutaciones en el genoma bovino.

Con gran costo, el Granjero Juan obtuvo las secuencias de los genomas de sus vacas. Cada genoma es una cadena de longitud ~M~ construida de cuatro caracteres ~A, C, G~ y ~T~. Cuando el alinea los genomas de sus vacas, él obtiene una tabla como la siguiente, mostrada aquí para ~N=3~ y ~M=8~:

Posiciones:         1 2 3 4 5 6 7 8

Vaca con Manchas 1: A A T C C C A T
Vaca con Manchas 2: A C T T G C A A
Vaca con Manchas 3: G G T C G C A A

Vaca sin Manchas 1: A C T C C C A G
Vaca sin Manchas 2: A C T C G C A T
Vaca sin Manchas 3: A C T T C C A T

Mirando cuidadosamente esta tabla, él se da cuenta que la sucesión desde la posición 2 hasta la posición 5 es suficiente para explicar las manchas. Esto es, mirando a los caracteres simplemente en esas posiciones (esto es, posiciones ~2...5~), el Granjero Juan puede predecir cual de sus vacas tiene manchas y cual no. Por ejemplo, si el ver los caracteres ~CTCG~ en estas posiciones, él sabe que la vaca debe tener manchas.

Por favor ayude a GJ a encontrar la longitud de la secuencia más corta de posiciones que puede explicar las manchas.

Entrada

La primera línea de la entrada contiene ~N~ y ~M~. Las siguientes ~N~ líneas contienen una cadena de ~M~ caracteres; ellos describen los genomas de las vacas con manchas. Las ~N~ líneas finales describen los genomas de las vacas sin manchas. Ninguna vaca con manchas tiene exactamente el mismo genoma que una vaca sin manchas.

Salida

Por favor imprima la longitud de la secuencia más corta de posiciones que es suficiente para explicar las manchas. Una secuencia de posiciones explica las machas si la existencia o no de manchas puede predecirse con exactitud perfecta dentro de la población de las vacas del Granjero Juan mirando simplemente esas posiciones en el genoma.

Restricciones

• ~1 \leq N \leq 500~
• ~3 \leq M \leq 500~

Ejemplo de Entrada

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

Ejemplo de Salida

4

USACO 2017 US Open Contest, Gold Problem 1. Bovine Genomics.