시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB126545.455%

문제

São dados uma string A de comprimento N e um conjunto S contendo M strings.

Uma permutação cíclica Bi de A, onde i é um número entre 1 e N, é a string

Bi = AiAi+1···AN-1ANA1A2···Ai-2Ai-1

e a sua pontuação é definida como o maior comprimento de uma substring de Bi que é também uma substring de uma string em S.

Uma substring é definida como uma sequência contígua de letras. Por exemplo, ab e dc são substrings de abfdc, mas ad e fc não são substrings de abfdc.

Sua tarefa é calcular a menor pontuação dentre todas as permutações cíclicas da string A.

입력

A primeira linha contém dois inteiros positivos N e M, (1 ≤ N ≤ 105, 1 ≤ M ≤ 104), representando o comprimento da string A e o tamanho do conjunto S, respectivamente.

A segunda linha contém a string A.

Cada uma das M linhas seguintes contém uma string si, representando a i-ésima string em S.

Todas as strings contêm apenas letras minúsculas do alfabeto, e é garantido que a soma dos tamanhos de todas as strings em S nunca ultrapassa 105 caracteres.

출력

Imprima uma linha contendo um inteiro representando a menor pontuação dentre todas as permutações cíclicas da string A.

예제 입력 1

7 3
acmicpc
acm
icpc
maratona

예제 출력 1

3

예제 입력 2

11 4
competition
oncom
petition
ztxvu
fmwper

예제 출력 2

5

예제 입력 3

12 4
latinamerica
zyvu
okp
wsgh
kqpdb

예제 출력 3

0