Genomica bovina (Oro)#10527

Genomica bovina (Oro)

1 secondo

128 megabyte

Difficile

Il Fattore John possiede $n$ mucche pezzate e $n$ mucche senza macchie. Avendo recentemente completato un corso di genetica bovina, è convinto che le macchie sulle sue mucche siano causate da mutazioni nel genoma.

Pagando parecchio denaro, il Fattore John ha determinato i genomi di tutte le sue mucche. Ogni genoma è una stringa di lunghezza $m$ composta dai quattro caratteri $A, C, G$ A, C, G e $T$ . Disponendo i genomi delle mucche uno sotto l'altro, ottiene la tabella riportata di seguito, per il caso $n = 3$ n = 3 e $m = 8$ m = 8:

Positions: 1 2 3 4 5 6 7 8

Spotty Cow 1: A A T C C C A T
Spotty Cow 2: A C T T G C A A
Spotty Cow 3: G G T C G C A A

Plain Cow 1: A C T C C C A G
Plain Cow 2: A C T C G C A T
Plain Cow 3: A C T T C C A T

Esaminando attentamente questa tabella, nota che la sequenza di posizioni da $2$ a $5$ è sufficiente per distinguere le mucche pezzate da quelle senza macchie. In altre parole, considerando solo i caratteri in queste posizioni (cioè le posizioni $2 \dots 5$ ), il Fattore John può determinare in modo univoco se una mucca è pezzata oppure no. Ad esempio, se in queste posizioni osserva la sequenza $GT C G$ , sa che la mucca è necessariamente pezzata.

Aiuta il Fattore John a determinare la lunghezza della più breve sequenza continua di posizioni che permette di distinguere le mucche pezzate da quelle senza macchie.

Input

Nella prima riga sono contenuti $n (1 \leq n \leq 500)$ n~(1 \le n \le 500) e $m (3 \leq m \leq 500)$ m~(3 \le m \le 500). Nelle successive $n$ righe sono contenute le stringhe di lunghezza $m$ che descrivono i genomi delle mucche pezzate. Nelle ultime $n$ righe sono contenuti i genomi delle mucche senza macchie. Nessuna mucca pezzata ha un genoma completamente identico a quello di una mucca senza macchie.

Output

Stampa la lunghezza della più breve sequenza continua di posizioni che sia sufficiente per distinguere le mucche pezzate da quelle senza macchie. Una sequenza di posizioni permette di distinguere le mucche pezzate da quelle senza macchie se la caratteristica «pezzatura» può essere determinata con precisione del cento per cento per tutte le mucche del Fattore John, considerando solo tali posizioni dei loro genomi.

Esempi

Esempio 1