I. Repetition
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

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

Examples
Input
2 2
aaaaaababab
ababaaaaaabab
aa
Output
4
Input
2 3
aaaaaababab
ababaaaaaabab
ab
Output
4
Input
2 5
aaaaa
aaaa
b
Output
-1
Note

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.