409779: GYM103741 I Repetition

Walk_alone loves repetition! He has a lot to say, and he may repeat some information in every sentence (represented as $$$n$$$ strings $$$S_1,S_2,\dots, S_n$$$) he says. Since such information could be important, his teammates want to extract a substring which appears in every sentence for at least $$$k$$$ times. However, some information (represented as string $$$T$$$) is so sensitive that they would not allow it to appear in the information. It is hard to find out the longest information they can extract, so they ask you for help.

Formally, you are given $$$n$$$ strings $$$S_1,S_2,\dots,S_n$$$ and a pattern $$$T$$$. Your task is to find the length of the longest string which appears in every $$${S}_i\ (1\le i\le n)$$$ for at least $$$k$$$ times, and does not have $$$T$$$ as its continuous substring.

The first line contains two integers $$$n\ (1\le n \le 10^5)$$$ and $$$k\ (1 \leq k \leq 10^5)$$$.

The $$$i$$$-th of the following $$$n$$$ lines contains a string $$${S}_i\ (|S_i|\ge 1,\, \sum_{i=1}^n|{S}_i|\le 10^6)$$$.

The last line contains a string $$$T\ (1\le |T|\le 10^5)$$$.

It is guaranteed that all strings contain only lowercase English letters.

Output an integer representing the answer. If such string does not exist, output $$$-1$$$ instead.

2 2
aaaaaababab
ababaaaaaabab
aa

4

2 3
aaaaaababab
ababaaaaaabab
ab

4

2 5
aaaaa
aaaa
b

-1

In the first example, 'abab' appears in both strings for $$$2$$$ times, so the answer is $$$4$$$. Note that though 'aaaaa' is longer, it has 'aa' as its substring.