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

문제

You are given a string A of length N and a set S, containing M strings.

A cyclic permutation Bi of A, in which i is between 1 and N, is the string

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

and its score is defined as the maximum length of a substring of Bi that is also a substring of some string in S.

A substring is defined as a contiguous sequence of letters. For example, ab and dc are substrings of abfdc, but ad and fc aren’t substrings of abfdc.

Your task is to calculate the minimum score over all cyclic permutations of string A.

입력

The first line contains two positive integers N and M, (1 ≤ N ≤ 105, 1 ≤ M ≤ 104), representing the length of the string A and the size of the set S, respectively.

The second line contains the string A.

Each of the next M lines contains one string si, representing the i-th string in S.

All strings contain only lowercase English letters and it’s guaranteed that the sum of lengths of all strings in S never exceeds 105 characters.

출력

Output an integer representing the minimum score over all cyclic permutations of 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